線性時間 在計算複雜性理論一個被稱為線性時間或 Οn時間的演算法表示此演算法解題所需時間與輸入資料的大小成正比通常以n表示換句話說執行時間與輸入資料大小為線性比例例如將一列數字加總的所需時間正比於串列的長度 然而實際情況常有差距真實的執行時間很可能與預期的比率相差甚大尤其在n的值很小時在技術討論時在足夠大的量n之下演算法的執行時間從 a n displaystyle an 到 b n displaystyle bn aｂ為正實數時就可稱線性時間詳情請看大O符號 達到線性時間的執行效能通常是一個演算法的最佳目標來源請求很多學者研究並創造了許多接近線性或更佳的演算法包括了軟體或硬體方面的研究硬體方面藉由諸如平行運算的硬體架構使得某些數學認為無法在標準計算模型下達到線性時間的演算法現在都可以在線性時間內執行完畢例如內容可定址記憶體英语Contentaddressable memory 某些排序演算法可以在特殊的資料結構及排列下擁有線性時間的效率但在一般情況下以比較元素大小來排序的演算法最多只能到達Οnlogn最低限度複雜性的證明已被小O符號含括通用排序演算法被認為是Ωn logn另外要找到一個集合中最大的元素是 Ωn因為演算法必須至少比較過n次才能找到最大元素 任何必須依賴全部輸入內容才能得解的問題它最少也得要線性時間才能得解因為它至少得花線性時間來讀取輸入資料