|
線性時間在計算複雜性理論，一個被稱為線性時間或 Ο(n)時間的演算法，表示此演算法解題所需時間與輸入資料的大小成正比，通常以n表示。換句話說，執行時間與輸入資料大小為線性比例。例如將一列數字加總的所需時間，正比於串列的長度。 然而實際情況常有差距，真實的執行時間很可能與預期的比率相差甚大，尤其在n的值很小時。在技術討論時，在足夠大的量n之下演算法的執行時間從到（a、ｂ為正實數）時，就可稱線性時間。詳情請看大O符號。 達到線性時間的執行效能通常是一個演算法的最佳目標[來源請求]。很多學者研究並創造了許多接近線性或更佳的演算法，包括了軟體或硬體方面的研究。硬體方面，藉由諸如平行運算的硬體架構，使得某些數學認為無法在標準計算模型下達到線性時間的演算法，現在都可以在線性時間內執行完畢。例如內容可定址記憶體）。 某些排序演算法可以在特殊的資料結構及排列下擁有線性時間的效率。但在一般情況下以比較元素大小來排序的演算法，最多只能到達Ο(nlog(n))。最低限度複雜性的證明已被小O符號含括；通用排序演算法被認為是Ω(n log(n))。另外，要找到一個集合中最大的元素是 Ω(n)，因為演算法必須至少比較過（n-1）次才能找到最大元素。 任何必須依賴全部輸入內容才能得解的問題，它最少也得要線性時間才能得解，因為它至少得花線性時間來讀取輸入資料。 參閱 |
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
