提示詞庫
效率估算器
計算函數和演算法的時間複雜度。
將此提示複製到我們的開發者 Console 來親自試試看！
| 內容 | |
|---|---|
| System | 你的任務是分析提供的函數或演算法，並使用大 O 符號計算其時間複雜度。請逐步解釋你的推理過程，描述你是如何得出最終時間複雜度的。在確定時間複雜度時，要考慮最壞情況。如果函數或演算法包含多個步驟或巢狀迴圈，請提供每個步驟的時間複雜度，然後給出整個函數或演算法的總體時間複雜度。除非另有說明，否則假設使用的任何內建函數或操作的時間複雜度都是 O(1)。 |
| User | def example_function(n): for i in range(n): print(i) for j in range(n): for k in range(n): print(j, k) |
輸出範例
為了分析給定函數
example_function(n)的時間複雜度，我們將其分解為多個步驟並考慮最壞情況。步驟 1：分析第一個迴圈
這個迴圈迭代
n次，並在每次迭代中執行一個常數時間操作（print(i)）。因此，這個步驟的時間複雜度是 O(n)。步驟 2：分析巢狀迴圈
外層迴圈迭代
n次，對於每次迭代，內層迴圈也迭代n次。在內層迴圈的每次迭代中，都執行一個常數時間操作（print(j, k)）。因此，巢狀迴圈的時間複雜度是 O(n * n) = O(n^2)。步驟 3：組合時間複雜度
函數example_function(n)由兩個步驟組成：第一個迴圈和巢狀迴圈。總體時間複雜度是每個步驟時間複雜度的總和。第一個迴圈的時間複雜度：O(n)
巢狀迴圈的時間複雜度：O(n^2)要確定總體時間複雜度，我們考慮增長階數最高的主導項。在這種情況下，O(n^2) 主導 O(n)。
因此，函數
example_function(n)的總體時間複雜度是 O(n^2)。在最壞情況下，當
n很大時，巢狀迴圈將主導執行時間，該函數將具有二次時間複雜度。