Ma connaissance du big-O est limitée, et lorsque les termes du journal apparaissent dans l'équation, cela me décourage encore plus.

Quelqu'un peut-il peut-être m'expliquer en termes simples ce qu'est un O(log n)algorithme? D'où vient le logarithme?

Cela s'est spécifiquement produit lorsque j'essayais de résoudre cette question de pratique à mi-parcours:

Soit X (1..n) et Y (1..n) deux listes d'entiers, chacune triée par ordre non décroissant. Donnez un algorithme en temps O (log n) pour trouver la médiane (ou le nième plus petit entier) de tous les 2n éléments combinés. Par exemple, X = (4, 5, 7, 8, 9) et Y = (3, 5, 8, 9, 10), alors 7 est la médiane de la liste combinée (3, 4, 5, 5, 7 , 8, 8, 9, 9, 10). [Astuce: utilisez les concepts de la recherche binaire]

Je dois admettre que c'est assez étrange la première fois que vous voyez un algorithme O (log n) ... d'où vient ce logarithme? Cependant, il s'avère qu'il existe plusieurs façons d'obtenir un terme de journal pour apparaître dans la notation big-O. Voici quelques-uns:

Diviser à plusieurs reprises par une constante

Prenez n'importe quel nombre n; dis 16. Combien de fois pouvez-vous diviser n par deux avant d'obtenir un nombre inférieur ou égal à un? Pour 16, nous avons ça

16 / 2 = 8
 8 / 2 = 4
 4 / 2 = 2
 2 / 2 = 1

Notez que cela prend quatre étapes pour terminer. Fait intéressant, nous avons aussi ce log ₂ 16 = 4. Hmmm ... qu'en est-il de 128?

128 / 2 = 64
 64 / 2 = 32
 32 / 2 = 16
 16 / 2 = 8
  8 / 2 = 4
  4 / 2 = 2
  2 / 2 = 1

Cela a pris sept étapes et log ₂ 128 = 7. Est-ce une coïncidence? Nan! Il y a une bonne raison à cela. Supposons que nous divisions un nombre n par 2 i fois. Ensuite, nous obtenons le nombre n / 2 ⁱ . Si nous voulons résoudre la valeur de i où cette valeur est au plus 1, nous obtenons

n / 2 ⁱ ≤ 1

n ≤ 2 ⁱ

log ₂ n ≤ i

En d'autres termes, si nous choisissons un entier i tel que i ≥ log ₂ n, alors après avoir divisé n en deux fois i, nous aurons une valeur au plus égale à 1. Le plus petit i pour lequel cela est garanti est à peu près log ₂ n, donc si nous avons un algorithme qui divise par 2 jusqu'à ce que le nombre devienne suffisamment petit, alors nous pouvons dire qu'il se termine par des étapes O (log n).

Un détail important est que peu importe la constante par laquelle vous divisez n (tant qu'elle est supérieure à un); si vous divisez par la constante k, il faudra log _k n pas pour atteindre 1. Ainsi, tout algorithme qui divise à plusieurs reprises la taille d'entrée par une fraction aura besoin de O (log n) itérations pour se terminer. Ces itérations peuvent prendre beaucoup de temps et donc le runtime net n'a pas besoin d'être O (log n), mais le nombre d'étapes sera logarithmique.

Alors, d'où vient ce problème? Un exemple classique est la recherche binaire , un algorithme rapide pour rechercher une valeur dans un tableau trié. L'algorithme fonctionne comme ceci:

• Si le tableau est vide, retournez que l'élément n'est pas présent dans le tableau.
• Autrement:
  • Regardez l'élément du milieu du tableau.
  • S'il est égal à l'élément recherché, renvoie succès.
  • S'il est supérieur à l'élément recherché:
    • Jetez la seconde moitié du tableau.
    • Répéter
  • S'il est inférieur à l'élément recherché:
    • Jetez la première moitié du tableau.
    • Répéter

Par exemple, pour rechercher 5 dans le tableau

1   3   5   7   9   11   13

Nous examinerions d'abord l'élément du milieu:

1   3   5   7   9   11   13
            ^

Puisque 7> 5 et que le tableau est trié, nous savons pertinemment que le nombre 5 ne peut pas être dans la moitié arrière du tableau, nous pouvons donc simplement le rejeter. Cela laisse

1   3   5

Alors maintenant, nous regardons l'élément du milieu ici:

1   3   5
    ^

Depuis 3 <5, nous savons que 5 ne peut pas apparaître dans la première moitié du tableau, nous pouvons donc lancer le premier demi-tableau pour quitter

        5

Encore une fois, nous regardons le milieu de ce tableau:

        5
        ^

Puisque c'est exactement le nombre que nous recherchons, nous pouvons signaler que 5 est bien dans le tableau.

Alors, à quel point est-ce efficace? Eh bien, à chaque itération, nous jetons au moins la moitié des éléments de tableau restants. L'algorithme s'arrête dès que le tableau est vide ou que nous trouvons la valeur souhaitée. Dans le pire des cas, l'élément n'est pas là, donc nous continuons à réduire de moitié la taille du tableau jusqu'à ce que nous manquions d'éléments. Combien de temps cela prend-il? Eh bien, puisque nous continuons à couper le tableau en deux encore et encore, nous le ferons dans au plus O (log n) itérations, car nous ne pouvons pas couper le tableau en deux fois plus de O (log n) fois avant de démarrer hors des éléments du tableau.

Les algorithmes qui suivent la technique générale de diviser-pour-conquérir (couper le problème en morceaux, résoudre ces morceaux, puis remettre le problème ensemble) ont tendance à contenir des termes logarithmiques pour cette même raison - vous ne pouvez pas continuer à couper un objet en moitié plus de O (log n) fois. Vous voudrez peut-être regarder le tri par fusion comme un excellent exemple de cela.

Traitement des valeurs un chiffre à la fois

Combien de chiffres le nombre n en base 10 contient-il? Eh bien, s'il y a k chiffres dans le nombre, alors nous aurions que le plus grand chiffre est un multiple de 10 ^k . Le plus grand nombre à k chiffres est 999 ... 9, k fois, et ceci est égal à 10 ^{k + 1} - 1. Par conséquent, si nous savons que n contient k chiffres, alors nous savons que la valeur de n est au plus 10 ^{k + 1} - 1. Si nous voulons résoudre k en fonction de n, nous obtenons

n ≤ 10 ^{k + 1} - 1

n + 1 ≤ 10 ^{k + 1}

log ₁₀ (n + 1) ≤ k + 1

(log ₁₀ (n + 1)) - 1 ≤ k

D'où nous obtenons que k est approximativement le logarithme en base 10 de n. En d'autres termes, le nombre de chiffres dans n est O (log n).

Par exemple, réfléchissons à la complexité de l'ajout de deux grands nombres trop gros pour tenir dans un mot machine. Supposons que nous ayons ces nombres représentés en base 10, et nous appellerons les nombres m et n. Une façon de les ajouter est d'utiliser la méthode de l'école primaire - écrivez les nombres un chiffre à la fois, puis travaillez de droite à gauche. Par exemple, pour ajouter 1337 et 2065, nous commencerions par écrire les nombres comme

    1  3  3  7
+   2  0  6  5
==============

Nous ajoutons le dernier chiffre et portons le 1:

          1
    1  3  3  7
+   2  0  6  5
==============
             2

Ensuite, nous ajoutons l'avant-dernier chiffre ("avant-dernier") et portons le 1:

       1  1
    1  3  3  7
+   2  0  6  5
==============
          0  2

Ensuite, nous ajoutons le troisième au dernier chiffre ("antépénultième"):

       1  1
    1  3  3  7
+   2  0  6  5
==============
       4  0  2

Enfin, nous ajoutons le chiffre du quatrième au dernier ("préantepenultimate" ... j'aime l'anglais):

       1  1
    1  3  3  7
+   2  0  6  5
==============
    3  4  0  2

Maintenant, combien de travail avons-nous fait? Nous effectuons un total de O (1) travail par chiffre (c'est-à-dire une quantité de travail constante), et il y a O (max {log n, log m}) chiffres totaux qui doivent être traités. Cela donne un total de complexité O (max {log n, log m}), car nous devons visiter chaque chiffre des deux nombres.

De nombreux algorithmes obtiennent un terme O (log n) en travaillant un chiffre à la fois dans une base. Un exemple classique est le tri par base , qui trie les entiers un chiffre à la fois. Il existe de nombreuses variantes de tri par base, mais elles s'exécutent généralement au temps O (n log U), où U est le plus grand entier possible qui est trié. La raison en est que chaque passage du tri prend O (n) temps, et il y a un total de O itérations (log U) nécessaires pour traiter chacun des chiffres O (log U) du plus grand nombre trié. De nombreux algorithmes avancés, tels que l'algorithme des chemins les plus courts de Gabow ou la version de mise à l'échelle de l' algorithme de débit maximal de Ford-Fulkerson , ont un terme logique dans leur complexité car ils fonctionnent un chiffre à la fois.

Quant à votre deuxième question sur la façon dont vous résolvez ce problème, vous voudrez peut-être vous pencher sur cette question connexe qui explore une application plus avancée. Compte tenu de la structure générale des problèmes décrits ici, vous pouvez maintenant avoir une meilleure idée de la façon de penser aux problèmes lorsque vous savez qu'il y a un terme logique dans le résultat, donc je vous déconseille de regarder la réponse tant que vous ne l'avez pas donnée. certains ont pensé.

J'espère que cela t'aides!

Lorsque nous parlons de descriptions big-Oh, nous parlons généralement du temps qu'il faut pour résoudre des problèmes d'une taille donnée . Et généralement, pour des problèmes simples, cette taille est simplement caractérisée par le nombre d'éléments d'entrée, et elle est généralement appelée n, ou N. (évidemment ce n'est pas toujours vrai - les problèmes avec les graphes sont souvent caractérisés par le nombre de sommets, V et nombre d'arêtes, E; mais pour l'instant, nous parlerons de listes d'objets, avec N objets dans les listes.)

Nous disons qu'un problème "est grand-Oh de (une fonction de N)" si et seulement si :

Pour tout N> quelque N_0 arbitraire, il existe une constante c, telle que le temps d'exécution de l'algorithme est inférieur à cette constante c fois (une fonction de N.)

En d'autres termes, ne pensez pas aux petits problèmes où la "surcharge constante" de la mise en place du problème compte, pensez aux gros problèmes. Et en pensant à de gros problèmes, grand-Oh de (une fonction de N) signifie que la période de temps est encore toujours inférieure à quelques temps de cette fonction constante. Toujours.

En bref, cette fonction est une borne supérieure, jusqu'à un facteur constant.

Donc, "big-Oh of log (n)" signifie la même chose que j'ai dit ci-dessus, sauf que "une fonction de N" est remplacée par "log (n)".

Donc, votre problème vous dit de penser à la recherche binaire, alors réfléchissons-y. Supposons que vous ayez, disons, une liste de N éléments qui sont triés par ordre croissant. Vous voulez savoir si un numéro donné existe dans cette liste. Une façon de faire ce qui n'est pas une recherche binaire consiste simplement à scanner chaque élément de la liste et à voir si c'est votre numéro cible. Vous pourriez avoir de la chance et le trouver du premier coup. Mais dans le pire des cas, vous vérifierez N fois. Ce n'est pas une recherche binaire, et ce n'est pas grand-Oh de log (N) car il n'y a aucun moyen de la forcer dans les critères que nous avons esquissés ci-dessus.

Vous pouvez choisir cette constante arbitraire pour être c = 10, et si votre liste contient N = 32 éléments, tout va bien: 10 * log (32) = 50, ce qui est supérieur à l'exécution de 32. Mais si N = 64 , 10 * log (64) = 60, ce qui est inférieur à la durée d'exécution de 64. Vous pouvez choisir c = 100, ou 1000, ou un milliard, et vous serez toujours en mesure de trouver un N qui enfreint cette exigence. En d'autres termes, il n'y a pas de N_0.

Si nous faisons une recherche binaire, cependant, nous choisissons l'élément du milieu et faisons une comparaison. Ensuite, nous jetons la moitié des chiffres, et le faisons encore, et encore, et ainsi de suite. Si votre N = 32, vous ne pouvez le faire qu'environ 5 fois, ce qui est log (32). Si votre N = 64, vous ne pouvez le faire qu'environ 6 fois, etc. Vous pouvez maintenant choisir cette constante arbitraire c, de telle sorte que l'exigence soit toujours remplie pour les grandes valeurs de N.

Avec tout ce contexte, ce que O (log (N)) signifie généralement est que vous avez un moyen de faire une chose simple, ce qui réduit de moitié la taille de votre problème. Tout comme la recherche binaire ci-dessus. Une fois que vous avez réduit le problème en deux, vous pouvez le couper en deux encore, encore et encore. Mais, surtout, ce que vous ne pouvez pas faire, c'est une étape de prétraitement qui prendrait plus de temps que ce temps O (log (N)). Ainsi, par exemple, vous ne pouvez pas mélanger vos deux listes en une seule grande liste, à moins que vous ne trouviez également un moyen de le faire en O (log (N)).

(REMARQUE: Presque toujours, Log (N) signifie log-base-deux, ce que je suppose ci-dessus.)

Dans la solution suivante, toutes les lignes avec un appel récursif sont effectuées sur la moitié des tailles données des sous-tableaux de X et Y. Les autres lignes se font en temps constant. La fonction récursive est T (2n) = T (2n / 2) + c = T (n) + c = O (lg (2n)) = O (lgn).

Vous commencez par MEDIAN (X, 1, n, Y, 1, n).

MEDIAN(X, p, r, Y, i, k) 
if X[r]<Y[i]
    return X[r]
if Y[k]<X[p]
    return Y[k]
q=floor((p+r)/2)
j=floor((i+k)/2)
if r-p+1 is even
    if X[q+1]>Y[j] and Y[j+1]>X[q]
        if X[q]>Y[j]
            return X[q]
        else
            return Y[j]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q+1, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j+1, k)
else
    if X[q]>Y[j] and Y[j+1]>X[q-1]
        return Y[j]
    if Y[j]>X[q] and X[q+1]>Y[j-1]
        return X[q]
    if X[q+1]<Y[j-1]
        return MEDIAN(X, q, r, Y, i, j)
    else
        return MEDIAN(X, p, q, Y, j, k)

Le terme Log apparaît très souvent dans l'analyse de la complexité des algorithmes. Voici quelques explications:

1. Comment représentez-vous un nombre?

Prenons le nombre X = 245436. Cette notation de «245436» contient des informations implicites. Rendre ces informations explicites:

X = 2 * 10 ^ 5 + 4 * 10 ^ 4 + 5 * 10 ^ 3 + 4 * 10 ^ 2 + 3 * 10 ^ 1 + 6 * 10 ^ 0

Quelle est l'expansion décimale du nombre. Ainsi, la quantité minimale d'informations dont nous avons besoin pour représenter ce nombre est de 6 chiffres. Ce n'est pas une coïncidence, car tout nombre inférieur à 10 ^ d peut être représenté en d chiffres.

Alors, combien de chiffres sont nécessaires pour représenter X? C'est égal au plus grand exposant de 10 dans X plus 1.

==> 10 ^ d> X
==> log (10 ^ d)> log (X)
==> d * log (10)> log (X)
==> d> log (X) // Et le journal apparaît encore ...
==> d = sol (log (x)) + 1

Notez également que c'est la façon la plus concise de désigner le nombre dans cette plage. Toute réduction entraînera une perte d'informations, car un chiffre manquant peut être mappé à 10 autres numéros. Par exemple: 12 * peut être mappé à 120, 121, 122,…, 129.

2. Comment recherchez-vous un nombre dans (0, N - 1)?

En prenant N = 10 ^ d, nous utilisons notre observation la plus importante:

La quantité minimale d'informations pour identifier de manière unique une valeur comprise entre 0 et N - 1 = log (N) chiffres.

Cela implique que, lorsqu'on lui demande de rechercher un nombre sur la ligne entière, allant de 0 à N - 1, nous avons besoin d' au moins log (N) essaie de le trouver. Pourquoi? Tout algorithme de recherche devra choisir un chiffre après l'autre dans sa recherche du numéro.

Le nombre minimum de chiffres à choisir est log (N). Par conséquent, le nombre minimum d'opérations prises pour rechercher un nombre dans un espace de taille N est log (N).

Pouvez-vous deviner les complexités d'ordre de la recherche binaire, de la recherche ternaire ou de la recherche déca?
Son O (log (N))!

3. Comment triez-vous un ensemble de nombres?

Lorsqu'on lui a demandé de trier un ensemble de nombres A dans un tableau B, voici à quoi il ressemble ->

Éléments permutés

Chaque élément du tableau d'origine doit être mappé à son index correspondant dans le tableau trié. Donc, pour le premier élément, nous avons n positions. Pour trouver correctement l'index correspondant dans cette plage de 0 à n - 1, nous avons besoin de… opérations log (n).

L'élément suivant nécessite des opérations de journal (n-1), le journal suivant (n-2) et ainsi de suite. Le total devient:

==> log (n) + log (n - 1) + log (n - 2) +… + log (1)

Utilisation de log (a) + log (b) = log (a * b),

==> log (n!)

Cela peut être approximé à nlog (n) - n.
Qui est O (n * log (n))!

Nous concluons donc qu'il ne peut y avoir d'algorithme de tri qui puisse faire mieux que O (n * log (n)). Et certains algorithmes ayant cette complexité sont le populaire Merge Sort et Heap Sort!

Ce sont quelques-unes des raisons pour lesquelles nous voyons log (n) apparaître si souvent dans l'analyse de complexité des algorithmes. La même chose peut être étendue aux nombres binaires. J'ai fait une vidéo là-dessus.
Pourquoi log (n) apparaît-il si souvent lors de l'analyse de complexité des algorithmes?

À votre santé!

Nous appelons la complexité temporelle O (log n), lorsque la solution est basée sur des itérations sur n, où le travail effectué à chaque itération est une fraction de l'itération précédente, car l'algorithme travaille vers la solution.

Je ne peux pas encore commenter ... c'est nécro! La réponse d'Avi Cohen est incorrecte, essayez:

X = 1 3 4 5 8
Y = 2 5 6 7 9

Aucune des conditions n'est vraie, donc MEDIAN (X, p, q, Y, j, k) coupera les deux. Ce sont des séquences non décroissantes, toutes les valeurs ne sont pas distinctes.

Essayez également cet exemple de longueur paire avec des valeurs distinctes:

X = 1 3 4 7
Y = 2 5 6 8

Maintenant MEDIAN (X, p, q, Y, j + 1, k) coupera les quatre.

Au lieu de cela, je propose cet algorithme, appelez-le avec MEDIAN (1, n, 1, n):

MEDIAN(startx, endx, starty, endy){
  if (startx == endx)
    return min(X[startx], y[starty])
  odd = (startx + endx) % 2     //0 if even, 1 if odd
  m = (startx+endx - odd)/2
  n = (starty+endy - odd)/2
  x = X[m]
  y = Y[n]
  if x == y
    //then there are n-2{+1} total elements smaller than or equal to both x and y
    //so this value is the nth smallest
    //we have found the median.
    return x
  if (x < y)
    //if we remove some numbers smaller then the median,
    //and remove the same amount of numbers bigger than the median,
    //the median will not change
    //we know the elements before x are smaller than the median,
    //and the elements after y are bigger than the median,
    //so we discard these and continue the search:
    return MEDIAN(m, endx, starty, n + 1 - odd)
  else  (x > y)
    return MEDIAN(startx, m + 1 - odd, n, endy)
}