線性時間v.s.二次時間

通常，一些答案提到給定的解決方案是線性或另一個是二次方。線性時間v.s.二次時間

如何區別/識別什麼是什麼？

有人可以解釋這個，最簡單的方法，像我這樣的人還不知道嗎？

2013-08-02 Anthony Perot

當所花費的時間與所涉及的元素的數量呈線性增加時，方法是線性的。例如，一個for循環它打印的數組的元素是大致線性的：

for x in range(10): 
    print x

因爲如果我們打印範圍（100），而不是範圍（10），這將需要運行它的時間爲10倍更長的時間。你會看到很多時候被寫爲O（N），這意味着時間或計算資源來運行的算法是成正比N.現在

，假設我們想打印的兩個元素循環：

for x in range(10): 
    for y in range(10): 
     print x, y

對於每一個x，我去循環10次。出於這個原因，整個事情通過10x10 = 100打印（你可以通過運行代碼來看到它們）。如果不使用10，我使用100，現在該方法將執行100x100 = 10000。換句話說，該方法爲O（N * N）或O（N 2），因爲每當您增加元素的數量時，計算工作量或時間將隨着點數的平方而增加。

來源

2013-08-02 18:22:20 Jblasco

我只給這個答案的學分，因爲我只是要求一個簡單的方法來解釋這一點。但絕對所有的答案是非常好的和詳盡的。 –

您應該考慮將示例更改爲：「對於範圍（n）中的x」對於範圍（10）中的x是恆定時間，而不是線性。 – pepper

它們必須指的是運行時複雜性，也被稱爲Big O符號。這是一個非常大的話題來解決。我會從關於維基百科的文章開始：https://en.wikipedia.org/wiki/Big_O_notation

當我研究這個主題時，我學會做的事情之一是用不同大小的數據集來繪製我的算法的運行時間。當您繪製結果圖時，您會注意到該線或曲線可以分爲幾個增長順序之一。

瞭解如何對算法的運行時複雜性進行分類將爲您提供一個框架，以瞭解您的算法如何在時間或內存方面進行擴展。它將使您能夠鬆散地比較和分類算法。

我不是專家，但這幫助我開始了兔子洞。

這裏有增長的一些典型的命令：

O（1） - 恆定時間
O（log n）的 - 對數
爲O（n） - 線性時間
O（ N^2） - 二次
O（2^N） - 指數
爲O（n） - 階乘

如果維基百科文章難以下嚥，我強烈建議您觀看iTunes大學關於此主題的講座，並探討算法分析，大O符號，數據結構甚至操作計數的主題。

祝你好運！

來源

2013-08-02 18:17:55

您通常會根據輸入大小n（如果輸入是數組或列表）來爭論算法。對問題的線性解決方案是執行時間與n一致的算法，因此x*n + y，其中x和y是實數。 n以最高指數1出現：n = n^1。

對於二次解，n出現在2爲最高指數的項中，例如， x*n^2 + y*n + z。

對於任意的n，線性解在執行時間內的增長速度比二次方法慢得多。請參考Big O Notation。

來源

2013-08-02 18:20:40 Femaref

你沒有指定，但是當你提到一個解決方案它可能是你問關於二次和線性收斂。爲此，如果你有一個算法是迭代的生成近似值序列的收斂值，那麼你有二次收斂時，你也可以說

x(n) <= c * x(n-1)^2

一些利好不斷c。也就是說，在迭代n+1處的解決方案中的誤差小於迭代n處的誤差的平方。看到這個更全面的收斂速度定義更全面的介紹http://en.wikipedia.org/wiki/Rate_of_convergence

來源

2013-08-02 18:28:50 mathematician1975

線性時間v.s.二次時間

回答

相關問題