log (n) vs log (k) dans l'exécution d'un algorithme avec k <n

Question

J'ai de la difficulté à comprendre la différence entre log (k) et log (n) dans l'analyse de complexité.

J'ai un tableau de taille n. J'ai un autre nombre k < n qui est une entrée de l'algorithme (donc ce n'est pas une constante connue à l'avance). Quels sont les exemples d'algorithmes qui auraient log (n) vs ceux qui auraient log (k) dans leur complexité? Je ne peux penser qu'aux algorithmes qui ont log (n) dans leur complexité. Par exemple, mergesort a une complexité log (n) dans son analyse d'exécution (O (nlogn)).

Answer 1

Si votre algorithme prend une liste de taille n et un certain nombre de grandeur k < n, la taille d'entrée est de l'ordre de n + log(k) (en supposant k peut être du même ordre asymptotique de n). Pourquoi? k est un nombre représenté dans un système de valeur de position (par exemple, binaire ou décimal) et un nombre de grandeur k requiert de l'ordre de log k des chiffres à représenter. Par conséquent, si votre algorithme prend une entrée k et l'utilise d'une manière qui nécessite que tous ses chiffres soient utilisés ou cochés (par exemple, l'égalité est vérifiée, etc.) alors la complexité de l'algorithme entier est au moins de l'ordre de log k. Si vous faites des choses plus compliquées avec le nombre, la complexité pourrait être encore plus élevée. Par exemple, si vous avez quelque chose comme for i = 1 to k do ..., la complexité de votre algorithme est au moins k - peut-être plus élevé, puisque vous comparez à log k -bit nombre k fois (bien que i utilise moins de bits que k pour beaucoup/la plupart des valeurs de i, en fonction de la base).

Answer 2

Il n'y a pas d'explication «one-size-fits-all» pour savoir où un terme O (log k) pourrait apparaître.

Vous voyez parfois cette exécution se produire dans les algorithmes de recherche et de tri où vous n'avez besoin de réorganiser qu'une petite partie de la séquence. Par exemple, la fonction std::partial_sort de la bibliothèque standard C++, qui réorganise la séquence de façon à ce que les premiers k éléments soient triés et les autres dans un ordre quelconque O (n log k). Une façon de le mettre en œuvre est de maintenir un min-tas de taille au plus k et de faire n insertions/suppressions sur lui, qui est n opérations qui prennent chacune du temps O (log k). De même, il existe un algorithme O (n log k) -time pour trouver les k éléments les plus importants dans un flux de données, ce qui fonctionne en maintenant un maximum de k éléments au maximum. (Aucune de ces approches ne sont optimales, cependant - vous pouvez effectuer un tri partiel dans le temps O (n + k log k) en utilisant un algorithme de sélection linéaire et trouver de manière similaire les k premiers éléments d'un flux de données dans O (n).) M

Vous voyez aussi parfois cette exécution dans des algorithmes qui impliquent une stratégie de division et de conquête où la taille du problème en question dépend de certains paramètres de la taille d'entrée. Par exemple, le Kirkpatrick-Seidel algorithm pour calculer une coque convexe fait un travail linéaire par niveau dans une récurrence, et le nombre de couches est O (log k), où k est le nombre d'éléments dans la coque convexe résultante. Le travail total est alors O (n log k), ce qui en fait un algorithme sensible à la sortie.

Dans certains cas, un terme O (log k) peut apparaître parce que vous traitez une collection d'éléments un chiffre à la fois. Par exemple, radix sort a un temps d'exécution de O (n log k) lorsqu'il est utilisé pour trier n valeurs qui vont de 0 à k inclusivement, avec le terme log k résultant du fait qu'il y a des chiffres O (log k) dans le nombre k.Dans les algorithmes de graphes, où le nombre d'arêtes (m) est lié mais peut être indépendant du nombre de nœuds (n), vous voyez souvent des temps d'exécution comme O (m log n), comme c'est le cas si vous implement Dijkstra's algorithm with a binary heap.