0 
Algorithm-1 (A:array[p..q] of integer)
    sum, max: integer
    sum = max = 0
    for i = p to q 
        sum = 0
        for j = i to q 
            sum = sum + A[j]
            if sum > max then
                max = sum
    return max

ネストされたループは何回実行されますか？

最初のforループにはO(n)複雑さがあり、アルゴリズム全体の複雑さは全体でO(n^2)。ただし、漸化式を介してこれを証明するには、内部ループの正確な実行回数が必要です。

4

4 に答える 4

1

おそらくあなたが探していた答えではありません。実際、内側のループには O(n) があり、プログラム全体の複雑さは O(n^2) であることがわかりました。カウンターを投げて、内側のループでインクリメントするだけです。これにより、正確な実行回数が得られるはずです。

于 2012-11-01T02:17:14.120 に答える
1

正確な数が必要な場合は、内側のループが呼び出されます(n + n-1+ ...1) = n(n+1)/2 ~= O(n^2)

ここn = q-p

于 2012-11-01T02:17:47.743 に答える
1

Sum(i = 1 -> n, i)に等しいだけではありませんn(n+1)/2か？

あなたの場合、n = q-p+1、だからあなたは得る(q-p+1)(q-p+2)/2。

これを拡張すると、これを正しく行った場合、(q^2-qp+2q-pq+p^2-2p+q-p+2)/2=が得られます(q^2+p^2-2qp+3q-3p+2)/2。

于 2012-11-01T02:21:36.240 に答える
0

内側のループは q-i+1 回実行され、合計実行回数は

\sum{ i=p }^{ q } (q-i+1) = \sum{ k=1 }^{ q-p+1 } (k) = n * (n+1) /2

ここで、n = q-p+1 です。

于 2012-11-01T02:53:24.830 に答える