Sekvan paĝon! Antaŭan paĝon! Indekson! Instrukcion!

Pri kompliko

Oni distingas la komplikon de algoritmo (aŭ programo), kaj la komplikon de komputebla funkcio (en la Leksikona difino, «problemo»).

  1. Kompliko de algoritmo
  2. Kompliko de komputebla funkcio
  3. Kompliko de formala lingvo
Kompliko de algoritmo
Estu a programo de Turinga aŭtomato kaj estu eniga ĉeno x; tiam la temporisurco tempo(a,x) estas la nombro de paŝoj en la komputado laŭ a kun la donitaĵo x ĝis la halto, aŭ malfinio, se a(x) diverĝas. Do, la tempa kompliko de a estas entjera funkcio

Tsup[a](n) = maks|x|=n tempo(a,x),  n EN N

Simile, la spacrisurco spaco(a,x) estas la nombro de la memorrubandaj fakoj, uzataj de a en komputado super x, kaj la spaca kompliko de a estas

Ssup[a](n) = maks|x|=n spaco(a,x),  n EN N

Algoritmo, kies komplikmezuro estas barita de m-grada polinomo estas nomata polinome barita (m-orda); simile, iuj algoritmoj estas eksponenciale baritaj, ktp. Tiaj karakterizoj implicas, ke la algoritmo konverĝas.

Ĉar laŭ la supra difino la komplikon de algoritmo determinas la plej komplikaj komputoj, oni nomas ĝin la pinta kompliko (angle worst case complexity, france «complexité maximale»). En pli fajna studo de algoritmokonduto oni interesiĝas ankaŭ pri averaĝa kompliko (¬T[a], ¬S[a]; angle average case complexity, france «complexité moyenne»), karakterizanta la ekspektan komplikon por koncerna probablodistribuo de la donaĵoj; kaj pri la malpinta kompliko (Tsub[a], Ssub[a]; angle best case complexity, france «complexité minimale»), kiun determinas la plej favoraj donaĵoj:

Ssub[a](n) = min|x|=n spaco(a,x); Tsub[a](n) = min|x|=n tempo(a,x)

Ekz-e, la Rapida ordigo havas

Por la bobelmetoda ordigo la komplikoj estas resp.

TBOsub = O(n); ¬TBO=O(n²); TBOsup = O(n²)

Kompliko de komputebla funkcio
Ĝi estas la suba limo de la pintaj komplikoj de ĉiuj algoritmoj, komputantaj la koncernan funkcion f. Do, la pinta kompliko de programo a komputanta la funkcion f estas supra baro por la kompliko de f.
Kompliko de formala lingvo
Ĝi estas la kompliko de ties analiza funkcio.

Pri la komplikteorio

La komputado kies tempa aŭ spaca kompliko havas la grandoordon 2n (kie n iel karakterizas la longon de la enigaĵo) estas praktike neplenumeblaj. Eĉ la kompliko O(nk), por granda konstanto k, estas nepraktika. Tamen, kontraste al la eksponenciale komplikaj, la polinome komplikaj komputadoj en la teorio estas rigardataj realisma komputado.

Kompreneble, por fajna analizo de komputkompliko oni devas atenti la komputadan modelon: la komplikmezuro ja draste dependas je tio, kion oni rigardas elementa paŝo. Ĉe la metamatematika studo de komputeblo oni havas intereson uzi kiel eble plej simplan modelon; ekz-e Turingan aŭtomaton kun unu sola rubando, kun minimuma signaro (sufiĉas kodi ĉion en la unuuma nombrosistemo) ktp. Nu, la diferenco inter la komplikmezuroj de esence unu sama algoritmo, plenumata per aŭtomatoj simplega aŭ pli realisma (ekz-e la ĝenerala reĝistra aŭtomato), mem povas esti eksponenciala. Tio motivas intereson pri adekvata komputada modelo.

Sekvan paĝon Indekson Instrukcion