有問題我正在努力工作,非常感謝您的幫助!什麼是時間複雜度...在漸近分析中添加日誌
for (int j = 1 to n) {
k = j;
while (k < n) {
sum += a[k] * b[k];
k += log n;
}
}
外循環運行n次。我不確定如何在內部循環中處理k+= log n
。我的想法是,它是O(n^2)。向k添加log(n)並不完全得到額外的n個循環,但我認爲它小於O(n * log n)。很明顯,這只是一個猜測,並且在弄清楚如何以數學方式顯示的任何幫助將不勝感激!
多少次內部循環執行呢? '小區(第(n-j)的/的log(n))'。從那裏工作。 – 2011-05-02 20:55:25