在計(jì)算復(fù)雜性理論中，一個(gè)被稱為線性時(shí)間或 Ο(n)時(shí)間的算法，表示此算法解題所需時(shí)間與輸入資料的大小成正比，通常以n表示。執(zhí)行時(shí)間與輸入資料大小為線性比例。例如，將一列數(shù)字加總的所需時(shí)間，正比于串列的長(zhǎng)度。然而實(shí)際情況常有差距，真實(shí)的執(zhí)行時(shí)間很可能與預(yù)期的比率相差甚大，尤其在n的值很小時(shí)。在技術(shù)討論時(shí)，如果在足夠大的量n之下算法的執(zhí)行時(shí)間從an到bn（a、b為正實(shí)數(shù)）時(shí)，就可稱線性時(shí)間。詳情請(qǐng)看大O符號(hào)。
基本介紹
在計(jì)算復(fù)雜性理論，一個(gè)被稱為線性時(shí)間或 Ο（n）時(shí)間的算法，表示此算法解題所需時(shí)間正比于輸入資料的大小，通常以n表示。換句話說(shuō)，執(zhí)行時(shí)間與輸入資料大小為線性比例。例如將一列數(shù)字加總的所需時(shí)間，正比于串行的長(zhǎng)度。
然而實(shí)際情況常有差距，真實(shí)的執(zhí)行時(shí)間很可能與預(yù)期的比率相差甚大，尤其在n的值很小時(shí)。在技術(shù)討論時(shí)，在足夠大的量n之下算法的執(zhí)行時(shí)間從an到bn（a、b為正實(shí)數(shù)）時(shí)，就可稱線性時(shí)間。詳情請(qǐng)看大O符號(hào)。
內(nèi)容
達(dá)到線性時(shí)間的執(zhí)行效能通常是一個(gè)算法的最佳目標(biāo)。很多學(xué)者研究并創(chuàng)造了許多接近線性或更佳的算法，包括了軟件或硬件方面的研究。硬件方面，借由諸如平行運(yùn)算的硬件架構(gòu)，使得某些數(shù)學(xué)認(rèn)為無(wú)法在標(biāo)準(zhǔn)計(jì)算模型下達(dá)到線性時(shí)間的算法，如今都可以在線性時(shí)間內(nèi)執(zhí)行完畢。例如內(nèi)容可尋址內(nèi)存（Content-addressable memory）。
某些排序算法可以在特殊的數(shù)據(jù)結(jié)構(gòu)及排列下?lián)碛芯€性時(shí)間的效率。但在一般情況下以比較元素大小來(lái)排序的算法，最多只能到達(dá)。最低限度復(fù)雜性的證明已被小O符號(hào)含括；通用排序算法被認(rèn)為是。另外，要找到一個(gè)集合中最大的元素是，因?yàn)樗惴ū仨氈辽俦容^過(guò)次才能找到最大元素。
任何必須依賴全部輸入內(nèi)容才能得解的問(wèn)題，它最少也得要線性時(shí)間才能得解，因?yàn)樗辽俚没ň€性時(shí)間來(lái)讀取輸入資料。
常量時(shí)間
在計(jì)算復(fù)雜度理論中，常量時(shí)間是一種時(shí)間復(fù)雜度，它表示某個(gè)算法求出解答的時(shí)間在固定范圍內(nèi)，而不依照問(wèn)題輸入數(shù)據(jù)大小變化。
常量時(shí)間記為（采用大O符號(hào)）。數(shù)字1可以替換為任意常數(shù)。
舉例：
想在“訪問(wèn)數(shù)組上的元素”的問(wèn)題上達(dá)到常量時(shí)間，只要以元素的序號(hào)訪問(wèn)即可。
然而“在數(shù)組上搜索最小值”并不是一個(gè)常量時(shí)間問(wèn)題，因?yàn)檫@需要掃描數(shù)組上的每一個(gè)元素以尋找最小值及其位置，一般需要次訪問(wèn)。
參閱
- 常數(shù)時(shí)間
- 多項(xiàng)式時(shí)間
參考資料 >