Lorsque nous parlons grand-Oh descriptions, nous parlons habituellement le temps qu'il faut pour résoudre les problèmes d'un taille . Et habituellement, pour les problèmes simples, cette taille est juste caractérisée par le nombre d'éléments d'entrée, et c'est généralement appelé n, ou N. (évidemment ce n'est pas toujours vrai-- les problèmes avec les graphiques sont souvent caractérisés par le nombre de Sommets, V, et le nombre de bords, E; mais pour l'instant, nous allons parler de listes de 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 moins de que la constante c temps (une fonction de N.)

en d'autres termes, ne pensez pas à de petits problèmes où le "overhead constant" de la mise en place de la les problèmes comptent, pensez aux gros problèmes. Et quand on pense à de gros problèmes, big-Oh of (une fonction de N) signifie que le temps d'exécution est toujours toujours moins que certains temps constants que la fonction. Toujours.

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

ainsi, " big-Oh of log(n)" signifie la même chose que j'ai dit plus haut, sauf que "une certaine 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 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 ce qui est pas une recherche binaire est de simplement scanner chaque élément de la liste et voir si c'est votre nombre cible. Vous pourriez avoir de la chance et le trouver au premier essai. Mais dans le pire des cas, vous cochez N différent temps. Ce n'est pas une recherche binaire, et ce n'est pas un gros-Oh de log(N) parce qu'il n'y a aucun moyen de le 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 A N=32 éléments, vous êtes bien: 10*log(32) = 50, ce qui est plus grand que 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 pourrez toujours trouver quelque chose qui viole 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 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 ne pouvez le faire qu'environ 6 fois, etc. Maintenant, vous peut choisir cette constante arbitraire c, de sorte que l'exigence est toujours respectée pour les grandes valeurs de N.

avec tout ce fond, ce que o(log(N)) signifie habituellement est que vous avez un moyen de faire une chose simple, qui Coupe votre taille de problème en deux. Tout comme la recherche binaire fait ci-dessus. Une fois que vous coupez le problème à moitié, vous pouvez le couper en deux, encore et encore, et encore. Mais, de façon critique, ce que vous ne pouvez pas faire 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 liste en une seule grande liste, à moins que vous ne trouviez un moyen de le faire dans le temps O(log(N)), aussi.

(NOTE: presque toujours, Log (N) signifie log-base-deux, ce qui est ce que je suppose ci-dessus.)

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

vous commencez avec la 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)

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

ne peut pas encore commenter... necro il est! La réponse d'Avi Cohen est incorrecte, essayez:

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

aucune des conditions ne sont vraies, donc la médiane(X, p, q, Y, j, k) coupera les deux fives. Ce sont des séquences non décroissantes, toutes les valeurs ne sont pas distinctes.

essayez aussi cet exemple de longueur uniforme avec des valeurs distinctes:

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

maintenant médian (X, p, q, Y, j+1, k) coupera les quatre.

à la place j'offre cet algorithme, l'appeler avec la médiane(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)
}

le terme logarithmique apparaît très souvent dans l'analyse de la complexité de l'algorithme. Voici quelques explications:

1. Comment représenter un nombre?

permet de prendre le nombre X = 245436. Cette notation de "245436" contient des informations implicites. Expliciter cette information:

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

, Qui est l'expansion décimale du nombre. Donc, le minimum d'information nous devons représenter ce numéro est 6 chiffres. Ce n'est pas une coïncidence, car tout nombre inférieur à 10^d peut être représenté par les chiffres d .

donc combien de chiffres sont nécessaires pour représenter X? Thats é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 log apparaît de nouveau...

= = > d = plancher (log(x)) + 1

notez aussi que c'est le moyen le plus concis pour indiquer le nombre dans cette gamme. Toute réduction entraînera une perte d'information, car un chiffre manquant peut être mappé à 10 autres numéros. Par exemple: 12* peut être mappé à 120, 121, 122, ..., 129.

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

en prenant N = 10^D, nous utilisons notre observation la plus importante:

la quantité minimale d'information permettant d'identifier de façon unique une valeur comprise entre 0 et N - 1 = log(N) chiffres.

cela implique que, lorsqu'il est demandé de rechercher pour un nombre sur la ligne entière, allant de 0 à N - 1, nous avons besoin 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 qu'il doit choisir est log(N). D'où le nombre minimum d'opérations prises pour chercher un numéro dans un espace de taille N est log(N).

Pouvez-vous deviner l'ordre complexité 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 chiffres?

lorsqu'on demande de trier un ensemble de nombres A dans un tableau B, voici à quoi il ressemble - >

Éléments De Permute

chaque élément du tableau original doit être associé à l'index correspondant dans le tableau trié. Ainsi, 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...opérations log(n).

l'élément suivant nécessite des opérations log(n-1), le log suivant(n-2) et ainsi de suite. Le total se chiffre à être:

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



l'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 la fusion populaire tri et Tri tas!

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

pourquoi le log(n) apparaît-il si souvent lors de l'analyse de la complexité de l'algorithme?

santé!