5. Ordó jelölés és algoritmusok hatékonysága

●       Egy exponenciális (futásidejű) algoritmust sosem tudunk sikeresen lefuttatni.

• i

• h

●       Tudjuk, hogy P része coNP-nek, de azt nem, hogy valódi része-e.

• i

• h

●       Létezik gyorsabb algoritmus, számítás n hossz meghatározására, mint O(n^2).

• i

• h

●       Két NxN-es mátrix összeszorzása általában O(n^3)-os

• i

• h

●       Két n hosszú vektor általános esetben O(n) műveletigénnyel adható össze.

• i

• h

●       Tudjuk, hogy P része NP-nek, de azt nem, hogy valódi része-e.

• i

• h

●       Két n*n-es mátrix általános esetben O(n) műveletigénnyel adható össze.

• i

• h

●       Egy O(n)-es algoritmus tekinthető O(n^3)-osnak is (csak legfeljebb így nem mérünk élesen)

• i

• h

●       Egy O(n)-es algoritmus tekinthető O(n^2)-esnek is (csak legfeljebb így nem mérünk élesen)

• i

• h

●       A polinomiális algoritmusok nagy előnye az exponenciálisokhoz képest az, hogy nagy n-re is “kezelhetők” maradnak.

• i

• h