這段代碼是什麼？

最近我參加了一個考試，其中有一個問題：g的時間複雜度是多少？現在這段代碼是什麼？

int f(int *arr, int n, int m) 
{ 
    if(n == 0) 
    { 
     if(m == 0) 
      return 3; 

     return arr[m] + f(arr, n, m - 1); 
    } 

    return f(arr, n - 1, m); 
} 

int g(int *arr, int n) 
{ 
    return f(arr, n, n); 
}

，我和我的大多數朋友回答爲O（n），因爲有明確的f和別的2 * N個電話，但教授的答案是爲O（n^2）。有人可以向我解釋誰是對的？如果是他，你能解釋一下爲什麼？

來源

2017-03-11 nononoha

這是寫的O（n），你的分析是正確的。你確定你沒有錯誤地記錄問題，而內部調用是'f（arr，m，m-1）'？正如所寫，在內部調用'f（arr，n，m-1）'中引用'n'沒什麼意義，因爲那時'n'總是0. –

我仔細檢查過它，它是n而不是m。我懷疑這位教授實際上把它誤認爲是O，因此就說O（n^2）。 – nononoha

'O（n * m）'但是函數調用是'n == m'，所以它的'O（n^2）'。 –

編輯：

在後，我意識到，我是解決錯誤的問題。我正在解決的內部函數調用是f(arr, m, m - 1)。在這種情況下，時間複雜度確實是O（n²）。問題發佈的方式是，時間複雜度爲O（n）。不過，我會離開這個帖子，因爲這很可能是教授誤解它的方式。因此，下面的答案被寫成考試問題可能用於參考的方式。

考慮所採取的步驟：

呼叫遞歸f() N次，這意味着n == 0 N個已下降堆棧。
現在，在這個最低的函數調用中，我們可以輸入if語句。
我們再次調用f()，減少m，但通過使用m作爲第二個參數來維護原始n值。
在這個'新'遞歸堆棧中，我們必須先調用f() n（或m）次，然後才能將m再減1。
一旦m == 0，我們可以返回。

看看這個圖表，其中每個「單元」代表一個呼叫f()。當n == 0時，我們再次調用第三個參數並將m減1，所以我們下降一個級別。

由於在該圖中的矩形的面積爲n * m和m == n，這意味着，f()稱爲n²時間和碼具有O（N²）時間複雜度。

來源

2017-03-11 18:59:09

「我們再次調用f（），減少m，但保持原始的n值」 - 那是怎麼回事？在該通話時，n始終爲0. –

對不起，現在編輯該問題。似乎我正在解決錯誤的問題。這可能是它的目的。編輯將因此專注於此。 –

這段代碼是什麼？

回答

相關問題