要分析這段程式碼的時間複雜度，我們需要考慮每一個迴圈的運行次數以及每次迴圈內部操作的數量。以下是這段程式碼的分析：
程式碼分析
for (int i=0; i <= n; i++)
K[i] = 0;
for (i=0; i <= n; i++)
for (j=0; j <= n; j++)
K[i] += j;
第一部分：初始化迴圈
for (int i=0; i <= n; i++)
K[i] = 0;
- 這個迴圈從 i = 0 到 i = n，一共運行 n + 1 次。
- 每次迴圈內部操作（K[i] = 0）的時間複雜度為 O(1)O(1)O(1)。
- 總的時間複雜度為 O(n+1)=O(n)O(n + 1) = O(n)O(n+1)=O(n)。
第二部分：嵌套迴圈
for (i=0; i <= n; i++)
for (j=0; j <= n; j++)
K[i] += j;
- 外層迴圈從 i = 0 到 i = n，一共運行 n + 1 次。
- 內層迴圈從 j = 0 到 j = n，每次外層迴圈運行時，內層迴圈運行 n + 1 次。
- 內層迴圈內部操作（K[i] += j）的時間複雜度為 O(1)O(1)O(1)。
因此，嵌套迴圈的總時間複雜度為： (n+1)×(n+1)×O(1)=(n+1)2(n + 1) \times (n + 1) \times O(1) = (n + 1)^2(n+1)×(n+1)×O(1)=(n+1)2 簡化後的時間複雜度為 O(n2)O(n^2)O(n2)。
總時間複雜度
將兩部分的時間複雜度合併：
- 第一部分：O(n)O(n)O(n)
- 第二部分：O(n2)O(n^2)O(n2)
總的時間複雜度由這兩部分中的較大者決定，因此整段程式碼的時間複雜度為： O(n2)O(n^2)O(n2)
結論
這段程式碼的時間複雜度為 O(n2)O(n^2)O(n2)。
阿摩線上測驗
登入