時間複雜度

時間複雜度 (Time Complexity)

時間複雜度是一個描述程式或演算法執行時間的函數,以步驟次數計算,我們通常使用 Big O notation 來表示。我們都假設 n 足夠大,因此只計最高項係數並省略常數,考慮最糟的情況。

用途

一般的 Judge 一秒可跑 10^8 筆運算,如果想知道自己的程式會跑幾秒,就把題目 n 的範圍代入所估的複雜度中,再除以 10^8,然後再跟題目的秒數限制比對,就知道會不會 TLE 了。

舉例:O(n²)

假設 n 的最大範圍是 5000:

O({n}^2)={5000}^2=2.5\times{10}^{7}

然後再除以1秒所花的時間:

\frac{2.5\times{10}^{7}}{{10}^8}=0.25秒

可以在1秒內跑完!

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *