Petite-oh notation en détail, les devoirs CS, à l'exclusion affectation réelle

Question

Je suis assis ici avec cette mission dans un cours sur des algorithmes avec des ensembles de données massifs et l'utilisation de la notation Petit-Oh m'a obtenu confus, même si je suis parfaitement à l'aise avec Big-Oh.

Je ne veux pas une solution à la cession, et en tant que tel, je ne le présente pas. Au lieu de cela ma question est de savoir comment j'interprète la complexité du temps o (log n)

Je sais que de la définition, qu'un Un algorithme doit croître asymptotiquement plus lent que o (log n), mais je ne suis pas certain de savoir si cela signifie que l'algorithme doit être en cours d'exécution en temps constant ou si elle est encore autorisé à être log n sous certaines conditions, telles que c = 1 ou si elle est vraiment log (n-1) .

Say un algorithme durée est de O (log n) mais en fait, fait deux itérations et en tant que tel c = 2, mais 2 log * n est toujours O (log n) , ai-je raison quand je dis que cela ne tient pas pour Little-Oh?

Toute aide est grandement appréciée et si cela est strictement nécessaire à la clarification, je fournirai l'affectation

Answer 1

Pour dire f est 'petit-oh-de g' f = o(g), signifie que le quotient

|f(x)/g(x)|

0 approche comme x tend vers l'infini. Se référant à l'exemple de votre o(log n), cette classe contient des fonctions comme log x / log (log x), sqrt(log x) et beaucoup d'autres, donc o(log x) ne signifie pas vraiment O(1). D'autre part, log (x/2) = log x - log 2, donc

log (x/2) / log x = 1 - log 2 / log x -> 1

et log (x/2) est pas dans la o(log x) classe.

Answer 2

Pour Petit-Oh, f (x) ne doit pas être inférieure à g (x) pour tout x. Il doit être plus petite seulement après une certaine valeur de x. (Pour votre question, il est toujours permis d'être log n sous certaines conditions).

Par exemple:

 let f(x) = 5000x and g(x) = x^2

f (x) / g (x) lorsque x tend vers l'infini est 0, alors f (x) est litte-o de g (x). Cependant, pour x = 1, f (x) est supérieure à g (x). Seulement après x devient supérieure à 5000 g volonté (x) soit plus grand que f (x).

Qu'est-ce que peu o nous dit vraiment que g (x) croît toujours à un rythme plus rapide que f (x). Par exemple, regardez combien f (x) a augmenté entre x = 1 et x = 2:

 f(1) = 5000
 f(2) = 10000 - f(x) became twice as big

Maintenant, regardez g (x) sur le même intervalle:

 g(1) = 1
 g(2) = 4 - g(x) became four times bigger

Ce taux augmentera encore plus à de plus grandes valeurs de x. Maintenant, puisque g (x) augmente à un rythme plus rapide et parce que nous prenons x à l'infini, à un moment donné, il deviendra plus grand que f (x). Mais ce n'est pas ce que peu o concerne, il est tout au sujet du taux de variation.