我了解基本的時間復雜度，但我很難知道時間復雜度何時與日志相關。這是我對 HackerRank Ice Cream Parlor 問題的解決方案：https ://www.hackerrank.com/challenges/icecream-parlor/problem
def icecreamParlor(m, arr):
for i in range(len(arr)):
for k in range(i 1, len(arr), 1):
if arr[i] arr[k] == m:
return [i 1, k 1]
我的理解是嵌套回圈通常是 O(n^2); 但是，由于我沒有在第二個回圈中每次都遍歷整個串列，因此這種情況會改變嗎？當我從內部回圈中的 i 開始時，回圈通過它所花費的時間越來越少。這個的時間復雜度是多少？
uj5u.com熱心網友回復：
在頂層，您正在回圈N時間。對于i這些回圈中的每一個，您都會回圈M = N-i幾次。請注意，這意味著M平均為 N: 的一半(5 4 3 2 1 0) == (5 5 5 5 5)/2。所以整體時間復雜度為O(N * N/2)，相當于O(N*N)或O(N**2)。
uj5u.com熱心網友回復：
我推薦使用Big-O python lib！您只需要匯入它，您就可以在其中運行您的代碼 :) 這將在多個專案中為您提供幫助。繼續努力！
uj5u.com熱心網友回復：
這仍然是 O(n^2)。你的外回圈正在做 N 作業，而你的內回圈正在做 n-1 作業。
如果你要寫出每個回圈的 i 和 k 計數，你會得到這樣的結果 for len(arr) = 5
i = 1 k = 2,3,4,5
i = 2 k = 3,4,5
i = 3 k = 4,5
i = 4 k = 5
i = 5
這種 for 回圈的模式類似于三角形數字 ( https://en.wikipedia.org/wiki/Triangular_number )。從文章中找到任何給定 N 的三角形數的方法是 N 1 選擇 2。這給了我們公式 N(N 1)/2。漸近地，這個函式給了我們 O(n^2) 的行為
uj5u.com熱心網友回復：
它仍然是 O(n^2) - 它顯然會比 2 個嵌套回圈快，每個嵌套回圈有 n 次迭代，但你仍然有 2 個依賴于變數的回圈。如果您還有任何問題，請聯系我 :)
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/459259.html