如何找到函數的漸近階？

我必須按照漸近順序安排n.logn，log（log（n））等幾個函數，我不知道該怎麼做，有人可以幫我解決嗎？如何找到函數的漸近階？

我知道這不是一個「做我的作業」論壇，但我真的很感激，如果有人能幫我做到這一點！謝謝。

來源

2012-03-20 Led Zeppelin

這是一個嚴格的基於證明的數學課，或不太嚴格的編程類型的東西，或...？ – mfrankli 2012-03-20 02:02:23

這是一個針對碩士學生的「算法和數據結構」課程。除了實現排序算法，它沒有太多的編程。 – 2012-03-20 02:05:05

一種interesting reference你開始與...

恆定時間 - O（1）（例如如果確定的整數（二進制表示）是偶數還是奇數

對數時間 - O（log n）的（例如二進制搜索）

二次時間 - O（N2）（如冒泡排序，插入排序）

等...

來源

2012-03-20 01:57:29

函數的順序描述了一個函數尺度隨着輸入的大小增加的需求如何。因此，log（log（n））對於n的所有值都會比n.log（n）更好地擴展（更有效），因爲log（log（n））< n.log（n）。在實踐中，您還必須擔心隱藏的常量，這可能會極大地影響算法的性能（即9.log（n）= log（n），其中9將退出）。

有用的表可以在這裏找到：http://en.wikipedia.org/wiki/Big_O_notation#Orders_of_common_functions

來源

2012-03-20 01:58:40 lrAndroid

那麼我應該如何說明步驟？我應該假設像1,2,10等n的2-3個值，然後解決所有這些問題並安排它？ – 2012-03-20 02:02:57

問題具體是什麼問題？ – lrAndroid 2012-03-20 02:05:06

列出從最低漸近階到最高漸近階的下面的函數。（n），log（log（n）），[log（n）] 2，log（n2）。 – 2012-03-20 02:05:39

的功能採取比和當n趨向無窮大時計算出的比率的限制。如果比例不明顯，你可以使用L'Hopital的規則。

http://en.wikipedia.org/wiki/L%27Hôpital%27s_rule

那麼你也可以做數值檢查，看看你的結果是有道理的。對於上面的例子，（log（log（n）））/（n log（n））的極限是零，所以n log（n）增長得快得多！

來源

2012-04-12 04:49:32 thundersteele

如何找到函數的漸近階？

回答

相關問題