Geek asks and answers

Trying to understand Big-oh notation

Hi, I am very grateful for the help in recording Big-O. Tomorrow I will pass the exam, and while I can determine that f (x) is O (g (x)), I cannot say that I fully understand it.

The following question “ALWAYS” appears on the exam, and I really need to try and understand, the first part seems easy (I think). You just select the value for n, calculate them all on the clacker and put them in order? It seems easy, although I'm not sure. I find it difficult to find examples on the Internet.

From the lowest to the highest, what is the correct order of complexity O (n2), O (log2n), O (1), O (2n), O (n!), O (n log2 n)?

What is the worst computational complexity of a binary search algorithm on an ordered list of length n = 2k?

+3
source share
6

.

, O (n2), O (log2n), O (1), O (2n), O (n!), O (n log2 n)?

, . , lim(a/b), 1, , inf. 0 , .

n = 2k?

  • / Big-O.
  • best/worst Big-O.
  • .
+3

, . Big-O , , " n". , , O (n) == O ( 2n), , .

"- n ", , , , ( n.) , , , , , , , , "- n ", , ( n) , , . , "O (n)" .

O (2n) = O ( n)? , O ( n), , n , . n , O ( 2n) , O ( n), . , , , - , O ( n).

, : ", , , - . , ?" n O (2n) O ( n) n O ( n ^ 2) O ( 500n). n 10, n ^ 2 10 10 100, 500n - 500 10 5000. n, n . n 500, n 500. n 1000, n ^ 2 , 500n - " ". n , n ^ 2 - 1 000 000 000 000, 500n - - 500 000 000 - . , n , O ( n) n.

( , n , n ^ 2 , 500n - , , ? . , . ?)

, O ( kajillion n) O ( n * log n). - , " n", , , - n O(). , , , , .

-, n , O (n ^ 2 + 61n + 1682) = O ( n ^ 2), n ^ 2 , 61n, n , 61n , 61n 1682. O(), n .

, O (log10n) = O ( ( ) n), b, log10 ( x) = log_ b (* x *)/log_ b (10). , O ( log10n) = O ( log_b (x) * 1/(log_b (10)). 1/log_b (10) , , O ( n) .

+2

, , , . , , , .

, O (2n) O (n) - (2). - , .

n , n. Big O - , - n, n . , n = 2 n ^ 2 4 n! 2, n! , n ^ 2.

, , , .. O (f (n)) 3n ^ 2 + 2n + 5, 5 (), 2n (3n ^ 2 ), 3 ( ), O (n ^ 2)... , n ^ 2 , .

, n , log (n) , , n ^ a > n ^ b, a > b, 2 ^ n n ^ a, n! . (: , n , , n!.)

, ? , ( ). log2 (2k). , , , n . , O (log (n)) < O (n), , .

!

+1

, n . , .

, , " " " , n". :

  • O (n ^ a) - , O (n ^ b), a > b.
  • log (n) n
  • exp (n) n
  • ! , exp (kn)

, , .

, O (1), O (log n), O (2n) = O (n), O (n log n), O (n ^ 2), O (n!)

0

Big-O , . , , , , .

, . ( ) . , n+5, 2*n 4*n + 1/n O(n), g(n)=n , .

, . , O(2*n + 5) = O(2*n) = O(n), n . , , n , , . , , .

Big O .

0

. this , .

enter image description here

0

More articles:


All Articles