時間複雜度是一個描述程式或演算法執行時間的函數,以步驟次數計算,我們通常使用 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秒內跑完!