"kahendlogaritmi" - 1 õppematerjal

Algoritmi ajaline keerukus

seetõttu valime c=2 ja n>N 409. a) Näidata , et n! = O( n n ) seega peame näitama n!<=c* nn n!=1*2*3*...*nkahendlogaritmi eelmisest seosest n<= 2n saame log 2 n <= n tähistus- kasutatakse kahepoolsete piiride korral Etteantud funktsiooni g(n) korral tähistame f(n)= ( g ( n )) , kui funktsioonid f ja g täidavad tingimusi (s.t. leiduvad sellised C1 ja C2 ning N) C1 g ( n ) f ( n ) C 2 g ( n ) kõigi n>=N korral n2 Ül. 417. Näidata, et - 3n = ( n 2 ) 2 n2