この質問とその答えを得る方法を理解するのに苦労しています。どうやって 計算する 最悪の場合の実行時間？
次のプログラムの入力は、n個の整数A [1]···A [n]を含む配列Aです。 big-O表記を使用して、各プログラムの最悪の場合の実行時間を制限します。
問題1：
i = 1, total = 0
while i < n/2:
total = total + A[i]
i=i*2
問題2：
total = 0
S = the set {1,2,3,4...n}
for each subset T of S
for each element x in T
total = total + A[x]
問題3：
int i = 1, j = 1;
for i = 1 to n:
while (j < n && A[i] < A[j])
j++
数値の配列A [1] 、。のプレフィックスの合計。 。 。 、A [n]は2番目の配列B [1]、。 。 。 、B [n]ここで、
B [i] = j = 1からiまでの合計 A [j]
次の問題は、プレフィックスの合計を計算します。
問題4：
for i = 1 to n:
B[i] = 0;
for j = 1 to i:
B[i] += A[j]
問題5：
B[1] = A[1];
for i = 2 to n:
B[i] = B[i-1] + A[i]
回答：
回答№1は1問題1：
アルゴリズムは、各アクセスのポイントで一定時間の操作（加算）を実行し、そのアクセスは次の間に行われます。 i<n/2。以来 i 毎回2倍になり、その後は条件が保持されなくなります log(n/4) ステップなので、最悪の場合の時間計算量は O（log（n））（対数）.
問題2：
アルゴリズムは配列の各要素にアクセスします（x 擬似コードで）のサブセットにあるのと同じ回数 S、およびアクセスポイントで一定時間の操作を実行します。すべての要素が 2 ^（n-1） それ自体を含むサブセット、および n そのような要素なので、最悪の場合の時間計算量は O（n * 2 ^（n））（指数）.
問題3：
whileループの条件がチェックされるたびに、の値が i+j 増加する 1、および i+j 決して減少することはできません。以来 i+j 〜から始まる 2 そして決して通り過ぎることはできません 2n+1、アルゴリズムの全体的な複雑さは O（n）（線形）.
問題4：
の与えられた値に対して i、内側のループが実行されます i 回。さらに、 i 範囲は1からnであるため、1 + 2 + 3 + ... + n = n（n + 1）/ 2の一定時間計算（加算）を実行します。したがって、アルゴリズムの全体的な複雑さは次のようになります。 O（n ^ 2）（二次）.
問題5：
アルゴリズムはアクセスします n-1 配列の要素であり、各アクセス（加算）のポイントで定数時間操作を実行するため、最悪の場合の時間計算量は O（n）（線形）.