時間複雜度 (Time Complexity)

時間複雜度:利用「最高次方」判斷一個演算法的效率,我們通常使用 Big-O 符號,估最糟的情形。

用途

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

舉例:O(N²)

假設 N 的範圍最大是 5000:

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

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

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

可以在一秒內跑完!

分享文章!
發佈留言

發佈留言必須填寫的電子郵件地址不會公開。