最近的一對點蠻力;爲什麼O（n^2）？

對於「最近對點」的問題（見this如果不熟悉的話），爲什麼運行蠻力算法的時間最壞情況爲O（n^2）？

如果說n = 4，那麼在搜索空間中只有12個可能的點對比較，如果我們也考慮比較任一方向的兩個點。如果我們不比較兩點，那麼它將是6.

O（n^2）不合計給我。

2017-01-17 user3407764

'n = 3'怎麼樣？ 'n = 5'怎麼樣？ – arekolek

步數與O（n^2）成正比，它們不必相等。 – Lee

實際比較次數爲n*(n-1)/2。這相當於n^2/2-n/2。但是，在大O符號中，你只關心占主導地位的術語。在非常大的值n下，-n/2術語變得不那麼重要，術語中的1/2係數也變得不那麼重要。所以，我們只是說它是O(n^2)。

大O符號並不意味着給你準確的時間或步驟數。它只會給你複雜性/時間的順序，所以你可以瞭解它如何針對大量輸入進行擴展。

來源

2017-01-17 19:49:32

而我們不關心繫數的原因是我們總是可以購買/建立一臺速度更快或速度更慢的計算機。或者我們可以更耐心。 :) – biziclop

偉大的一點。而且，你可以很容易地得到一個好的實現和一個不好的算法實現之間的差異。 –

在大O符號，則可以分解出相乘常數，因此：

O(k*(n^2)) = O(n^2)

的想法是，（在OP例如1/2時，由於距離的比較是反射性的）的常數不真的告訴我們關於複雜性的新東西。它仍然會隨着輸入的平方變大。

來源

2017-01-17 19:45:02 danh

在算法的蠻力版本中，您比較了所有可能的點對。對於n每個點你有(n - 1)其他點來比較，如果我們採取每一對一旦我們結束(n * (n - 1))/2比較。 O(n^2)的悲觀複雜性意味着對於某些常數k，操作的數量受k * n^2約束。大O符號無法告訴您操作的確切數量，但是當數據大小（n）增加時，它與其成比例的函數。

來源

2017-01-17 19:47:32 Ardavel

應用蠻力，我們被迫檢查所有可能的配對。假設N個點，每個點有N-1個我們需要計算距離的點。因此計算的總可能距離= N點* N-1個其他點。但在過程中，我們加倍計算距離。 A到B之間的距離保持是否計算A到B或B到A.因此N *（N-1）/ 2。因此O（N^2）。

來源

2017-01-17 19:50:59 Abhi7950

最近的一對點蠻力;爲什麼O（n^2）？

回答

相關問題