找不到這個C代碼的時間複雜度？

-2

我很難找出如何計算一些代碼的時間複雜度。我知道大O的基本知識，儘管我不能完全理解如何計算。找不到這個C代碼的時間複雜度？

這是一個我無法解決的例子。希望你能：

void f(int n) { 
    int j, s; 
    for (j = 0, s = 1; s < n; j++, s*=2) 
     printf(「!」); 
    double values[j]; 
    for (int k = 0; k < j; k++) 
     values[k] = 0; 
    while (j--) 
     for (int k = 1; k < j; k++) 
      values[k] += 1.0/k; 
}

什麼是運行時間？我很喜歡解釋:)

來源

2016-02-13 sadasas sadsadas

什麼是運行時或大O複雜度？ – juanchopanza

@juanchopanza哦，不知道這是兩回事。像O（logn）或O（n^2）這樣的計算，如果它對你來說意味着什麼。對困惑感到抱歉。 –

一個好的開始可能是格式化代碼，使其更具可讀性。在C中，空白並不重要（字符串和字符文字之外），所以縮進對於編譯器*來說並不重要。儘管如此，它對人類非常重要。 –

第一個循環迭代log2(n)次，計算j，最高位的順序爲n。複雜性O(log(n))。

第二個循環初始化一個大小爲j的數組：時間和空間複雜度爲O(log(n))。

第三回路是嵌套循環與嵌套循環迭代j到1次，總共j * (j - 1)/2次迭代j倍。這個時間複雜度爲O(log(n)^2)，並且支配了之前的階段。

該功能的整體時間複雜度爲O(log(n)^2)，空間複雜度爲O(log(n))。

來源

2016-02-13 12:18:12 chqrlie

終於有人用了。非常感激。謝謝。 –

找不到這個C代碼的時間複雜度？

回答

相關問題