どのようにアルゴリズムの複雑さを解決するには？

Question

私はアルゴリズムの分析のための2つの質問があり、次の2つの複雑さを決定する方法を知っているしたいと思います：

まず：

For(int i=2; i<n; i=i*i*i) 
{ 
    //something O(1) 
} 

第二：

n/1 + n/2 + n/3 +...+ n/n 

Answer 1

最初に：

1*1*1 = 1だから私は常に1であり、決して>= nではないので、無限になります。

2番目のアルゴリズムは実際にはアルゴリズムではありませんが、加算はO(n)で実行されます。最初のアルゴリズムの

Answer 2

：

iの初期値（@tschaefemediaに述べたように無限ループにつながるのではなく1）2であるとするが。第1の反復において

、私第3の反復で2回目の反復では== 2

、I == 2 * 2 * 2 == 23

、I ==（23 * 23 * （3 * 3）* 2（3 * 3）== 2（3 * 3 * 3）== 2（3 * 3）

第4反復では、 3）反復k + 1での

...

、I == 2（3 * 3 * 3 * ... * 3）== 2（3K）

簡略化のために、反復k-1でiがnに等しくなり、ループが停止すると仮定します。その後：

N == 2（3K）

LOG2（N）== 3^K

LOG3（LOG2（N））== K

したがって、複雑性はOであります（log3（log2（n）））

2番目の質問は複雑な式を与えていると思います。だから、

N/1 + N/2 + N/3 + ... + N/N = N（1 + 1/2 + 1/3 + ... + 1/N）

これは、ハーモニックシリーズであり、それはO（）N（ログ）

そうで、全体の複雑さはO（N *ログ（n））を