Algorithm_BIG_O

Question

我需要帮助理解/做大O符号.我理解它的目的,我不知道如何确定复杂性.下面是我目前从通过年度论文中检索的几个例子,在考试之前做了修改!我已经提供了一些问题的答案,请帮我检查一下是否正确,tq!##

1. 例1:

   for (int i = 0; sqrt(i) < n; i++) 
       cout << i << endl;
   

Answer 1

1. 代码将运行直到sqrt(i)> = n,这意味着i> = n ^ 2所以它是 O(n^2)
2. 外循环运行n次,内循环运行log(n),这样就可以了 O(n*log(n))
3. 第一个循环是O(n),之后k的值是2 ^ n所以第二个循环是O(2 ^ n)所以总的来说它是 O(n) + O(2^n) = O(2^n)