int func (int n, int m)
{
if (n<1)
return n;
else if (n<10)
return func(n-m, m);
else
return func(n-1, m);
}
這就是功能。什么是大 O 表示法，我該如何計算它？我對此很陌生。
有這方面的一般規則嗎？
uj5u.com熱心網友回復：
O(n)。我也是學生，所以對此持保留態度。如果錯了，我會洗掉這個。但我認為這是對的。嘗試查找理論并理解它，以便將其應用于所有問題。
它將需要 n-10 次回圈 nm 次回圈 1 次回圈，大約是 n，在大 O 中你忽略小錯誤——例如，它更接近 n 而不是 n^2。
uj5u.com熱心網友回復：
這個答案來自cplusplus com中另一個叫jonnin的人。這是：
“遞回只是一種回圈，你用同樣的方式對待它。痛點是有時很難理解回圈，但你也可以寫出令人討厭的普通回圈，所以這是雙方的問題。
這基本上是這個回圈，用于計算完成的實際作業：（如果不熟悉遞回，可能需要一段時間才能看到它） while(n > 10) n --;
如果 N < 10 則不執行任何操作，否則在 O(n) 時遞減。您可以具體說明 N<10 個特殊情況，但大 O 是關于事物的一般意義，而不是血淋淋的細節。如果你想布局所有細節，就像關于一些奇異函式的 PHD 論文，你可以深入挖掘并這樣做，但大多數大 O 分析是一種更粗糙的工具。作為一名教師，我會接受 O(n)，因為 N>10，否則 O(1)。
如前所述，如果允許 M 為 0/負數，則永遠不會結束，您也應該注意這一點。這很可能是錯誤的輸入，不應影響答案 (?)。”
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/537111.html
標籤：递归时间复杂性理论减少
上一篇：計算串列串列中的元素并將答案作為Prolog中的串列輸出
下一篇：在深層嵌套陣列（樹）中查找遞回