Et par spørsmål om algoritmer

[Knut Marius]

Skal opp til eksamen i videregående programvareutvikling i morgen, og har ikke lest alt for mye. Pensum går delvis på javaprogrammering (som jeg føler jeg har ganske grei kontroll på) og delvis på algoritmer (sortering, søk, komprimering, trær/grafer osv). Siste delen sliter jeg litt med.

 

Jeg har et par spørsmål angående algoritmekompleksitet:

 

Sitat fra forelesningsnotatene mine: "P = NP? Man har ikke klart å finne noe slik algoritme, og dette er det viktigste åpne spørsmålet i informatikk. Er P = NP?"

 

Kan noen forklare meg hva i hule heiteste P = NP egentlig betyr?

Og hva er egentlig "Big-O"?

 

Mulig jeg kommer med et par andre spørsmål her i løpet av kvelden. Setter stor pris på seriøse svar

Endret 12. mai 2005 av knutmarius

[Manoz]

Står noe her -> http://en.wikipedia.org/wiki/Complexity_classes_P_and_NP

 

Selv har jeg ikke peiling