Ce serait provoquer un algorithme d'avoir O(log n) la complexité?

Question

Ma connaissance de big-O est limitée, et quand le journal termes apparaissent dans l'équation, il me jette encore plus. Quelqu'un peut peut-être m'expliquer le commun des mortels ce qu'est un O(log n) l'algorithme est? D'où vient le logarithme viennent.

Cela concerne en particulier les est venu quand j'ai essayé de résoudre cette mi-parcours de la pratique question:

Soit X(1..n) et Y(1..n) contient deux listes d'entiers, chaque triés dans nondecreasing commande. Donner un O(log n) en temps de l'algorithme pour trouver la médiane (ou le n-ième plus petit entier) de l'ensemble des 2n combinaison des éléments. Pour ex, X = (4, 5, 7, 8, 9) et Y = (3, 5, 8, 9, 10), puis 7 est la médiane de la liste (3, 4, 5, 5, 7, 8, 8, 9, 9, 10). [Conseil: utiliser les concepts de la recherche binaire]

Answer 1

Je suis d'accord que c'est assez bizarre la première fois que vous voyez un O(log n) algorithme... où sur la terre, n'est que le logarithme venir? Cependant, il s'avère qu'il y a plusieurs façons différentes que vous pouvez obtenir un journal terme pour apparaître dans les big-O de notation. Voici quelques-unes:

À plusieurs reprises division par une constante

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

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

Notez que cela prend quatre étapes. Fait intéressant, nous avons aussi ce log₂ 16 = 4. Hmmm... que dire 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 connectez-vous₂ 128 = 7. Est-ce une coïncidence? Nope! Il y a une bonne raison à cela. Supposons que l'on divise un nombre n par 2 i fois. Alors nous obtenons le nombre n / 2^je. Si nous voulons résoudre pour la valeur de i, si cette valeur est à 1, on obtient

n / 2ⁱ ≤ 1

n ≤ 2ⁱ

log₂ n ≤ i

En d'autres termes, si nous choisissons un entier i tel que i ≥ log₂ n, puis après la plongée de n par 2, j'fois, nous allons avoir une valeur qui est au plus 1. Le plus petit i pour ce qui est garanti, c'est à peu près log₂ n, donc si nous avons un algorithme qui divise par 2 jusqu'à ce que le nombre devient suffisamment petit, on peut dire qu'il se termine en O(log n) étapes.

Un détail important, c'est qu'il n'a pas d'importance ce que la constante que vous êtes en divisant n par (tant qu'il est supérieur à un); si vous divisez par la constante k, il faudra log^k n étapes pour atteindre 1. Ainsi, n'importe quel algorithme qui à plusieurs reprises divise la taille par une fraction aurez besoin de O(log n) itérations pour résilier. Ces itérations peut prendre beaucoup de temps et donc, le net runtime n'ai pas besoin de O(log n), mais le nombre d'étapes est logarithmique.

D'où vient donc ce sont en place? Un exemple classique est celui de la recherche binaire, un algorithme rapide pour une recherche dans un tableau trié pour une valeur. L'algorithme fonctionne comme ceci:

• Si le tableau est vide, le retour que l'élément n'est pas présent dans le tableau.
• Sinon:
  • Regardez le centre de l'élément de la matrice.
  • Si elle est égale à l'élément que nous sommes à la recherche pour, revenir réussite.
  • Si il est plus grand que l'élément que nous recherchons:
    • Jeter de la deuxième moitié du tableau.
    • Répétez
  • Si c'est moins que le l'élément que nous recherchons:
    • Jeter la première moitié du tableau.
    • Répétez

Par exemple, pour rechercher dans le tableau 5

1   3   5   7   9   11   13

Nous aimerions d'abord, regardez le centre de l'élément:

1   3   5   7   9   11   13
            ^

Depuis le 7 > 5, et depuis le tableau est trié, nous savons pour un fait que le numéro 5 ne peut pas être dans la moitié arrière de la matrice, de sorte que nous pouvons simplement de l'ignorer. Cela laisse

1   3   5

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

1   3   5
    ^

Depuis 3 < 5, nous savons que la 5 ne peuvent pas apparaître dans la première moitié du tableau, nous pouvons jeter la première moitié de tableau de quitter

        5

De nouveau, nous regardons le milieu de ce tableau:

        5
        ^

Car c'est exactement le nombre que nous recherchons, nous pouvons signaler que 5 est en effet dans le tableau.

Alors, quelle est l'efficacité de cette? Ainsi, à chaque itération, nous allons jeter au moins la moitié des éléments du tableau. L'algorithme s'arrête dès que le tableau est vide ou nous trouvons la valeur que nous voulons. Dans le pire des cas, l'élément n'est pas là, donc nous garder de réduire de moitié la taille de la matrice jusqu'à ce que nous sommes à court d'éléments. Combien de temps cela prend-il? Eh bien, puisque nous garder de coupe le tableau en deux, encore et encore, nous nous en au plus O(log n) itérations, puisque nous ne pouvons pas couper le tableau en deux plus de O(log n) fois avant le terme des éléments d'un tableau.

Les algorithmes suivant la technique de diviser pour mieux régner (découpe le problème en morceaux, la résolution de ces morceaux, puis mettre le problème de retour ensemble) ont tendance à avoir des termes logarithmiques pour cette même raison, vous ne pouvez pas garder la coupe d'un objet dans la moitié plus de O(log n) fois. Vous voudrez peut-être chercher à fusionner sorte comme un bon exemple de cela.

Le traitement des valeurs à un chiffre à un moment

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

n ≤ 10,^k+1 - 1

n + 1 ≤ 10^k+1

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

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

À partir de laquelle nous obtenons que k est environ le logarithme en base 10 de n. En d'autres termes, le nombre de chiffres de n est O(log n).

Par exemple, nous allons réfléchir sur la complexité de l'ajout de deux grands nombres qui sont trop gros pour rentrer dans une machine à mot. Supposons que nous ayons ces nombres représentés en base 10, et que nous appellerons les nombres m et n. Une façon d'ajouter est de passer par la primaire, la méthode d'écrire les nombres d'un chiffre à la fois, puis de travailler à partir de la droite vers la gauche. Par exemple, pour ajouter 1337 et 2065, nous aimerions commencer par écrire les nombres en tant que

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

Nous ajoutons le dernier chiffre et de porter l'1:

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

Nous ajoutons ensuite la deuxième à la dernière ("avant-dernier") chiffres et de porter l'1:

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

Ensuite, nous ajoutons de la troisième à la dernière ("antépénultième") chiffres:

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

Enfin, nous ajoutons de la quatrième à la dernière ("preantepenultimate"... j'adore l'anglais) chiffres:

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

Maintenant, combien de temps avons-nous fait? Nous faisons un total de O(1) par des chiffres (c'est-à-dire, une constante de la quantité de travail), et il y a O(max{log n, log m}) total des chiffres qui doivent être traitées. Cela donne un total de O(max{log n, log m}) de la complexité, parce que nous avons besoin de visiter chaque chiffre dans les deux chiffres.

De nombreux algorithmes d'obtenir un O(log n) terme de travail d'un chiffre à la fois dans une base. Un exemple classique est le tri radix, qui trie des nombres entiers d'un chiffre à la fois. Il y a beaucoup de saveurs de tri radix, mais ils ont l'habitude de fonctionner en temps O(n log U), où U est le plus grand entier qui est en cours de tri. La raison pour cela est que chaque passage de la sorte prend O(n) le temps, et il y a un total de O(log U) itérations nécessaires pour traiter chacun des O(log U) chiffres du plus grand nombre en cours de tri. De nombreux algorithmes avancés, tels que Gabow du plus court chemin algorithme ou la mise à l'échelle de la version de la Ford-Fulkerson max-algorithme de flux, un journal terme dans leur complexité, parce qu'ils travaillent un chiffre à la fois.

---

Quant à votre seconde question, comment vous résoudre ce problème, vous pouvez regarder cette question connexe , qui explore les plus avancées de l'application. Compte tenu de la structure générale des problèmes qui sont décrits ici, vous pouvez maintenant avoir une meilleure idée de la façon de penser au sujet des problèmes lorsque vous savez qu'il y a un journal terme dans le résultat, donc je ne vous le conseille de regarder la réponse jusqu'à ce que vous avez un peu réfléchi.

Espérons que cette aide!

Answer 2

Lorsque nous parlons de la grande-Oh descriptions, nous parlons habituellement le temps qu'il faut pour résoudre des problèmes de taille. Et généralement, pour des problèmes simples, que la taille est seulement caractérisé par le nombre d'éléments d'entrée, ce qui est habituellement appelé n ou N. (Évidemment ce n'est pas toujours vrai, des problèmes avec les graphes sont souvent caractérisés en nombre de sommets V, et le nombre d'arêtes, E; mais pour l'instant, nous allons parler des listes d'objets, avec N objets dans les listes.)

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

Pour tout N > arbitraire N_0, il existe une constante c, tels que le moteur d'exécution de l'algorithme est inférieure à la constante c temps (une fonction de N.)

En d'autres termes, ne pas penser à de petits problèmes où la "constante de frais généraux" de poser le problème des questions, de réfléchir à de gros problèmes. Et lorsque vous pensez à de gros problèmes, grand-Oh (fonction de N) signifie que le moment de l'exécution est encore toujours moins que certains constante de temps de la fonction. Toujours.

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

Ainsi, le "big-Oh de log(n)" signifie la même chose que j'ai dit ci-dessus, à l'exception d'une fonction de N" est remplacé par "log(n)."

Donc, votre problème vous dit de penser binaire de recherche, nous allons donc réfléchir à cela. Supposons que vous avez, disons, une liste de N éléments sont triés dans l'ordre croissant. Vous voulez savoir si un nombre donnī existe dans cette liste. Une façon de faire qui n'est pas un binaire de recherche est de l'analyse de chaque élément de la liste et voir si il est votre numéro de cible. Vous pourriez avoir de la chance et de trouver du premier coup. Mais dans le pire des cas, vous constaterez N des moments différents. Ce n'est pas binaire de recherche, et il n'est pas grand-Oh de log(N), car il n'y a aucun moyen de le forcer dans les critères que nous avons esquissé ci-dessus.

Vous pouvez choisir que l'constante arbitraire c=10, et si votre liste a N=32 éléments, vous êtes amende: 10*log(32) = 50, ce qui est supérieur à la durée d'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 gazillion, et vous serez toujours en mesure de trouver un certain N qui contrevient à cette obligation. En d'autres termes, il n'y a pas de N_0.

Si nous faisons une recherche binaire, cependant, nous choisissons le moyen de l'élément, et de faire une comparaison. Puis nous jeter la moitié des numéros, et le faire 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 pouvez faire cela seulement environ 6 heures, etc. Maintenant, vous pouvez choisir que l'constante arbitraire c, de telle sorte que la condition est toujours satisfaite pour de grandes valeurs de N.

Avec tout ce que l'arrière-plan, ce que O(log(N)) signifie généralement que vous avez une certaine manière de faire une chose simple, qui réduit le problème de la taille de moitié. Tout comme le binaire de recherche est en train de faire ci-dessus. Une fois que vous coupez le problème à moitié, vous pouvez le couper en deux, encore et encore, et encore. Mais, surtout, ce que vous ne pouvez pas faire est de certains de prétraitement étape qui prendra plus de temps que que O(log(N)) de temps. Ainsi, par exemple, vous ne pouvez pas mélanger vos deux listes en une seule grosse liste, sauf si vous pouvez trouver un moyen de le faire en O(log(N)) de temps, trop.

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

Answer 3

Dans la solution suivante, toutes les lignes avec un appel récursif sont fait sur la moitié de la taille des sous-ensembles de X et Y. D'autres lignes sont en fait une constante de temps. La fonction récursive est T(2n)=T(2n/2)+c=T(n)+c=O(lg(2n))=O(lgn).

Vous commencez avec une MÉDIANE(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)