Big O Notation - 大小順序

2012-07-28 58 views 3 likes

我目前正在嘗試計算二次算法，三次算法和指數函數之間的主要量化差異。Big O Notation - 大小順序

我不明白的是什麼意思是「量化」，它真的在問什麼？我試圖尋找這方面的信息，但沒有運氣。

謝謝。

在顯示O（n2），O（n3）和O（2n）的數量級的表中顯示n = 1,2,4,10和20的近似對應值。什麼是相應的值？ – user1028145 2012-07-28 11:50:05

也許更好地嘗試http://cstheory.stackexchange.com/這裏有點OT – 2012-07-28 12:00:38

只需繪製一個表，其中n^2，n^3和2^n作爲列，並且每行增加n。然後填寫數值並查看它們的大小（http://simple.wikipedia.org/wiki/Order_of_magnitude） – 2012-07-28 12:02:34

回答

定量差異僅僅意味着數量上的差異 - 即這些不同類型的算法之間的大小差異是什麼？給出數字例子是個好主意，例如顯示一些示例問題大小的二次，三次和指數算法的運行時間。

2012-07-28 11:52:35

例如，如果我要使用值，n = 1 2 4 10和20.如何從這些值計算問題大小？ – user1028145 2012-07-28 12:02:50

n *是*問題大小 – 2012-07-28 12:08:11

@ user1028145：n是問題大小。對於二次問題，運行時間是n * n，對於三次方來說它是n * n * n，對於指數，它是e^n。 – 2012-07-28 12:10:40

當您使用大O表示法來估計算法的計算複雜性，的目標是提供一個定性洞察力在ň變化如何影響算法的性能ñ變大。

如果您消除其對總停止是顯著爲ñ變大的任何條款和消除任何持續性因素，我想你可以說，你只剩下主定量差異。

2012-07-28 11:56:02

相關問題