次のコードの時間複雑度はどのようにO（n）ですか？

私はInterview Bitで時間複雑度の問題を解決していました。次のコードの時間複雑度はどのようにO（n）ですか？

この質問に対する正解はO（N）です。しかし、私によれば、答えはO（NlogN）でなければなりません。最初の "forループ"の複雑さはO（logN）でなければならない。というのは、変数iが各反復で2で割られ、ループ変数が2で乗算されるか、または2で除算されるときはいつでも、時間の複雑さはO （logN）。さて、2番目の "forループ"について、複雑さはO（N）でなければならないので、最終的な複雑さはO（N * logN）でなければなりません。

誰でも私が間違っている場所を説明できますか？

出典

2017-02-14 DG4

O（NlogN）はO（）が上限であるため、実際には_wrong_ではありません。 O（N）よりも情報量が少ないです。 – Gassa

あなたが間違っていたのは、外側のループがO（log N）回入力されているときに、アルゴリズム全体がO（？* log N）を取っているという考えを提供すると、内側ループはcN時間の平均いくつかの定数cは、外側のループの各実行です。 IVladの答えが述べるように、あなたは幾何学的なシリーズにつながる数学をする必要があります。 – moreON

は、実際の数学の操作を行います。

T(N) = N + N/2 + N/4 + ... + 1 (log_2 N terms in the sum)

これは1/2比の幾何学的なシリーズですので、合計は以下に等しい。

T(N) = N*[1 - (1/2)^(log_2 N)]/(1 - 1/2) = 
    = [N - N/(2^log_2 N)]/0.5 = 
    2^log_2 N = N 
    = (N - 1)/0.5

のでT(N)はO(N)です。

出典

2017-02-14 10:20:38 IVlad

@IVIad、私はあなたがT（n）= O（n）を計算した方法を理解しました。しかし、私はあなたが外側forループのためだけに計算したと思います。しかし、内側ループのために何をすべきですか？ – DG4

@ DG4いいえ、それはプログラム全体です。 'i = N'のとき、内部は' N '回実行されます。 'i = N/2'のとき、内部は' N/2 '回実行されます。したがって、合計にはすべてが考慮されます。 – IVlad

次のコードの時間複雑度はどのようにO（n）ですか？

答えて

関連する問題