運行的算法時間，以秒

我明白了算法的運行時間在大O或大歐米加符號表達等等，但我仍然無法弄清楚秒（或毫秒）多久代碼被執行。例如，n = 10^6，我們做O（n），那麼我怎麼知道需要多長時間？我也明白，在for循環中的其他語句也會對運行時間有所貢獻，並且在不同的CPU上，時間可能會有所不同。但通常在編碼競賽中，我們會給出一個特定的時間，比如說2-5秒，在這裏我不能確定我的算法是否足夠高效或者讓我的代碼變慢。謝謝！運行的算法時間，以秒

來源

2015-10-19 Sreenidhi

你不知道需要多長時間。你只知道數字操作的數量級將發生。 – ergonaut

這不是O符號有多大的作用。它所指的是在添加'事物'時算法效率的縮放。

這不是絕對的時間，而是相對的。一個O（n）的100個物品只要10個物品就需要10倍。 O（N^2）意味着你會期望100倍的差異。（10^2 = 100,100^2 = 10,000）

而就是這樣。這是表達效率的一種方式，而不是計算運行時間。你仍然需要知道一個「操作」花了多長時間，這取決於處理器/架構。

參見： What is a plain English explanation of "Big O" notation?

「大O符號是一個算法的複雜性的相對錶示。」

來源

2015-10-19 17:03:33 Sobrique

謝謝！這有幫助！ – Sreenidhi

爲O（n）是不是真的意味着測試時間。這更多是對可擴展性的測試。有些事情可能需要數萬億次操作，但它仍然是O（1），因爲無論輸入大小如何，它都需要1萬億次操作。

跨規模測試時間的唯一方法是實際運行它，看到的輸入各種大小會發生什麼。

來源

2015-10-19 17:06:01

O形符號的優點是，它是機器無關的，它實際上是知道的算法比別人的高效與否的最好指標。請注意，計算機每年都會變得更快，所以現在得到的秒數的具體速度測量值將隨着時間而改變，但使用O-notation時，總是會清楚地知道，解決O（log n）中的問題比在上）。

但是，您仍然有很多工具來測量程序的（近似）速度執行時間。例如，在Linux中，您有time命令。儘管如此，結果還取決於許多其他變量（包括物理變量;例如，CPU溫度可能會降低程序的性能）。這是不可能來衡量，因爲環境的噪音的特定算法的確切時間度量（和它仍然是無用的，因爲它總是取決於在它運行的計算機上）。

來源

2015-10-19 17:13:41

@Andrew謝謝！但是，在比賽中，我們是如何堅持時間限制的？ – Sreenidhi

@Sreenidhi我不確定它是如何在競賽中工作的，但我猜測他們在同一臺機器上和相同條件下運行每個人的算法，所以他們可能已經檢查過，即使是「最差的可接受算法」在該機器的限制時間內運行。 –

運行的算法時間，以秒

回答

相關問題