Je sais que ce n'est pas strictement une question de programmation, mais il est une question de science informatique, donc j'espère que quelqu'un peut m'aider.
Je travaille sur mes algorithmes devoirs et déterminer le Big-Oh, Big-Omega, Theta, etc., de plusieurs algorithmes. Je les prouve en trouvant leurs valeurs C et N 0 et tout va bien.
Cependant, j'ai rencontré mes deux derniers problèmes dans l'ensemble et je me débatte de savoir comment les faire (et Google n'aide pas beaucoup).
Je n'ai pas eu à comprendre le Big-OH / OMEGA des sommations avant.
Mes deux derniers problèmes sont:
et
Ma question est, comment puis-je montrer ça?
Par exemple, dans la première, intuitivement, je ne peux pas voir comment cette sommation de I 2 est O (n 3 ). Le second me confond encore plus. Quelqu'un peut-il expliquer comment montrer le Big-Oh et la Big-Omega de ces sommations?
5 Réponses :
http://fr.wikipedia.org/wiki/big_o_notation
n répétitions de g (m) = O (f (m)) est somme de i = 1..n de i * g (i) est Définition: g (n) = O (f (n)) si certains c, m existent pour tous N> M, La somme est pour i = 1..n de Si f est monotonique dans i, cela signifie que chaque terme est <= i f (n) <= n f (n). Donc la somme est inférieure à Bien sûr, log_2 (x) et x ^ 2 sont à la fois monotonique. O (n * f (m)) pour n'importe quel f (n).
o (n * f (n)) si g (n) = O (f (n)) et f est monotonique.
g (n) <= c * f (n) < / p>
i * f (i) .
n * c * f (n) de sorte que la somme est o (n * f (n)) (témoigné par le même c, m que cela rend g (n) = o (f (n)))
Ce que j'ai écrit s'applique à la question, si vous prenez le fait que g (x) = x ^ 2 est en effet O (x ^ 2) et g (log_2 (x) est en effet O (log x).
mon devinez est que le point de question signifie que si vous résumez les résultats de certains calculs pour lesquels la durée de fonctionnement est proportionnelle à I 2 dans la première cas, et proportionnelle au journal 2 i dans le second cas. Dans les deux cas, la période de fonctionnement de la somme globale est "dominée" par les valeurs plus volumineuses de n dans la sommation, et donc l'évaluation globale de la BIG-O des deux sera N * O (F) où f est la fonction que vous " ressomme.
O (f) n'est qu'une notation pour les fonctions; Vous n'êtes pas obligé d'apporter des moments de course. :-)
O (f) est une notation pour comment les temps de fonctionnement des fonctions échelle - Je ne suis pas sûr de ce que vous entendez sur "apporter des temps de course", dès que vous parlez de la notation O Vous parlez déjà de temps de course en quelque sorte.
Non, o (f) est une notation pour la croissance d'une fonction. E.g., la fonction F (n) = N ^ 2 + 3 * N + 5 est O (n ^ 2). Cela n'a rien à voir avec les temps de course: dire que "F est O (n ^ 2)" est juste une déclaration sur le comportement asymptotique de F (n) comme n-> ∞, il n'y a aucune mention de calcul ou d'algorithmes ou de leur temps d'exécution.
D'accord, je suis corrigé à cet égard. En fait, je ne suis pas vraiment sûr de savoir pourquoi j'ai écrit ce que j'ai fait dans ce commentaire - je blâme les samedis paresseux. ;)
Probablement, votre CPU multipliera des entiers 32 bits en temps constant. Mais Big-Oh ne se soucie pas de "moins de quatre milliards", alors vous devez peut-être examiner des algorithmes de multiplication?
Selon Wolfram , l'algorithme de multiplication "traditionnel" est O (n 2 ). Bien que n dans ce cas est le nombre de chiffres, et donc vraiment log (n) dans le nombre réel. Je devrais donc être capable de faire carré les entiers 1..n dans le temps O (n.log (n)). Sommation est O (log (n 2 )), qui est évidemment O (journal (n)), pour une complexité globale de O (n.log (n)).
Je peux donc bien comprendre votre confusion.
Vous pensez à la multiplication réelle, qui est trop littérale. Je pense que la question dans le manuel implique est que je ^ 2 est en réalité la complexité d'une certaine opération. Si tel est le cas, alors O (N ^ 3) a du sens.
La réponse est bien mais elle répond à la mauvaise question. Astuce: Ce n'est pas une question sur le temps de course.
La question ne dit rien (ni ne demande) de temps de course. C'est juste une déclaration sur les fonctions: dans l'ancien cas, la somme (i = 1 à n) (i ^ 2) est la fonction n (n + 1) / 2, qui est O (n ^ 2). De même dans la seconde, la somme est LG (n!), Qui est O (n LG N).
La somme (i = 1 à n) (i) est la fonction n (n + 1) / 2, la somme (i = 1 à n) (i ^ 2) a une forme fermée plus compliquée, mais Wolfram Alpha fait tout plus simple;). Je veux dire que je pourrais résoudre la fonction génératrice, mais je digresse la somme (i = 1 à n) (i ^ 2) est la fonction 1/6 * (2 * N ^ 3 + 3 * n ^ 2 + n)
L'approche la plus simple qui me saute est une preuve par induction.
Pour le premier, il faut essentiellement montrer que si nous utilisons le principe généralisé d'induction et prendre un cas de base de n = 1 et k = 2. Nous obtenons Bien sûr Prenez l'hypothèse inductive, alors nous savons que Afficher maintenant Par conséquent, notre résultat initial est correct. pour la deuxième preuve dont vous avez besoin pour montrer que
L'étape principale est 1 <2 * 1 . somme (i = 1 à n) i ^ 2 somme (i = 1 à n) i ^ 2 + (n + 1) ^ 2
k * n ^ 3 + (n + 1) ^ 2 k * n ^ 3 + n ^ 2 + 2n + 1 k * n ^ 3 somme (i = 1 à n) log_2 (i)> = k * n * journal (n) , que je laisserai comme un exercice pour le lecteur;). somme (i = 1 à n) log_2 (i) + log_2 (n + 1)> = k * n * journal (n) + k * journal (n +1) , pour certains K, donc clairement k est 1.
σ (i = 1 à n) i 2 = n (n + 1) (2n + 1) / 6, qui est O (n 3 ).
Notez que (n!) 2 = (1 N) (2 (n-1)) (3 (n-2)) ... (N-1) 2) (n 1)
= Π (i = 1 à n) i (n + 1-i)
> = π (i = 1 à n) n
[Par exemple, parce que pour chaque I = 1 à N, (I-1) (NI)> = 0. Comparez avec Graham / Knuth / PataShnik , Section 4.4]
= n n .
Ainsi, n! > = n n / 2 , et donc
Σ (i = 1 à n) journal i = journal π (i = 1 à n) i = journal n! > = journal n n / 2 = =
(n / 2) journal n, qui est Ω (n journal n).
Juste pour clarifier - sont-ce une somme de I², ou une somme de quelque chose qui est O (n²)?
@Charlie Sels, tout ce que je dis, serait une supposition. C'est la 2 questions, dans leur intégralité.
Je pense que le premier est vrai si vous appliquez l'algorithme standard multiplication - pas utiliser le matériel
mul qui est une opération constante.Prenez-vous CS170 à Berkeley?
Voir Stackoverflow.com/q/9252891/632951