大きなOh表記を使用してプログラムの複雑さを書き込む方法は？

Question

「MITx：6.00.1x Pythonを使用したコンピュータサイエンスとプログラミング入門」から。

私はこのコースをやっていますし、クイズを解決する際に問題があります。私は非常に新しいプログラマーであり、プログラミングの考え方が十分ではありません。

最悪の場合にプログラム2を実行するのに必要なステップ数はいくらですか？入力xのサイズnで答えを表現する。

def program2(x): 
    total = 0 
    for i in range(1000): 
     total = i 

    while x > 0: 
     x = x//2 
     total += x 

    return total 

Answer 1

は

def program(x): 
    count = 0 
    while x > 0: 
     x = x // 2 
     count += 1 
    return count 

X = 2 ** 31 =>数= 32

X = 2 ** 10 =>数自体から答えを得るためにあなたのプログラムを書き換え

= 11

。 。 。

結果：O(log n)最良ケースのシナリオで

Answer 2

、xは、我々は最初の一歩のため= 0総割当を実行0以下です。次に、範囲（1000）のfor iループを実行します。このループは1000回実行され、各反復で3つのステップ（1つはループを介して毎回割り当てられ、もう1つは+ =操作のために2つのステップが割り当てられます）があります。次に、x> 0かどうかをチェックします。ループに入ることはありません。最良の場合、1 + 3 * 1000 + 1 + 1 = 3003ステップを実行するreturnステートメントにもう1つのステップを追加します。

最悪の場合のシナリオでは、xは大きな正の数です。この場合、最初に1ステップにつき割り当て合計= 0を実行します。次に、最初のループを1000回（合計3000ステップ）実行し、次に2回目のループ（x> 0）をn回実行します。このループには5つのステップがあります（1つは条件チェック用、x> 0、 - =および+ =演算用にそれぞれ2つ）。最終的にx = 0の地点に到達すると、前回の条件チェックx> 0を実行します。そうでないため、ループに入ることはありません。最悪の場合、1 + 3 * 1000 + 5 * n + 1 + 1 = 5 * n + 3003ステップを実行します。