在計算機科學中，時間複雜度是衡量一個演算法隨著輸入大小增加其運行時間增長情況的一種描述。當我們說到 Ω（歐米加）值的時候，我們通常是在談論演算法的下界時間複雜度。
具體來說：
Ω（Omega）表示法: 用來描述演算法執行時間的下限。當我們說一個演算法的時間複雜度是Ω(f(n))，意味著對於足夠大的n（輸入規模），這個演算法的運行時間至少是f(n)的倍數。換句話說，f(n)是這個演算法性能的一個保證，即演算法在最壞情況下至少這麼"快"。
用更正式的數學語言來說，如果存在正常數 c 和 n₀，對於所有的 n > n₀，演算法的運行時間 T(n) 滿足 c*f(n) ≤ T(n)，則我們說 T(n) 是 Ω(f(n))。
例如，如果一個演算法的時間複雜度是Ω(n)，意味著不管演算法如何，其執行時間都不會比n的線性增長慢。
Ω是對演算法的一種樂觀估計，與之相對的是：
O（大O）表示法: 用來描述演算法執行時間的上限。當我們說一個演算法的時間複雜度是O(f(n))時，意味著這個演算法的運行時間在最壞情況下不會超過f(n)的倍數。
Θ（Theta）表示法: 當一個演算法的時間複雜度同時被O(f(n))和Ω(f(n))緊緊夾住時，我們可以說演算法的時間複雜度是Θ(f(n))。這意味著演算法的運行時間在最壞情況下與最好情況下都會與f(n)成某種程度的比例。
這些符號讓我們能夠更精確地討論和分析演算法的性能，不僅僅是在最壞情況下，也包括在最好或者"典型"情況下的表現。
阿摩線上測驗
登入