ループ内の大きな複雑さ

Question

最初にn個のステップを実行し、次に2番目の時間、次のn-4番目のループを実行し、最後の時間まで繰り返していたループを持つアルゴリズムループは2ステップ実行しましたが、このループの複雑さの測定値は何ですか？

実行されていないステップの数が2次的に増加するため、これはO（n^2）の複雑さを示すと信じています。私はそのようなループそのものを視覚化するのに苦労しているので、私の答えがわからなくなってしまいます。

ヘルプ/任意の種類のセカンドオピニオンを大幅に理解される:)

Answer 1

あなたは複雑さがΘ（N ）あることが適切です。何を記述することであるので、これはarithmetic progression：

（N - 2）+（N - 4）+ ... + 2（または末尾の奇数）である

（、明らかに、2 + 4 + 6 + ... +（n-2）または奇数開始相当物BTW）。

formula for the sumを使用すると、最初と最後の要素の平均であり、要素の数を掛けたものです。これらの用語のそれぞれはΘ（n）であり、その製品はΘ（n ）です。