Overleg:Complexiteitsgraad

Ik blijf volhouden: Het beste sorteeralgoritme is hash-sort met O(n)! Rob Hooft 30 mrt 2003 21:13 (CEST)

Alleen in gedegenereerde gevallen, bv een pak kaarten dat moet worden gesorteerd dan kun je iedere kaart na inspectie meteen in het goede vakje leggen en zo in 1 pass het hele deck sorteren. Werkt alleen als de te sorteren stapel van te voren bekend is qua grootte en samenstelling. Hash sort is niet eens een echte sort. Evanherk 30 mrt 2003 21:19 (CEST)

Hashsort heeft niet complexiteit n, maar complexiteit n+k, waar k het aantal mogelijke waarden is. Voor veel sorteergevallen is k oneindig, voor veel andere gevallen veel groter dan n. Andre Engels 30 mrt 2003 23:10 (CEST)

---

kan " f(n)<a.n2 " toegelicht worden, wat is "a" ? Lvg 30 mrt 2003 22:51 (CEST)

Ik heb erbij gezet dat a een constante is. Ik hoop dat dat voldoende duidelijk is, zo niet, dan weet ik ook niet wat ik nog meer moet zeggen. Andre Engels 30 mrt 2003 23:12 (CEST)

Orde van sorteeralgoritmen

Er bestaan inderdaad algoritmen zoals Counting_sort met orde n+k < n log (n), maar deze werken alleen in specifieke gevallen zoals getallen en berusten niet op het onderling vergelijken van elementen. Het is bewezen (weet niet waar een bewijs te vinden is) dat een sorteeralgoritme dat gebaseerd is op het onderling vergelijken van elementen minimaal orde n log(n) heeft. (Je zou dus kunnen zeggen dat sorteren met vergelijking theta van n log(n) is). Het beste sorteeralgoritme voor objecten waarvan alleen een ordening bekend is (dus voor elk paar objecten a en b is gegeven dat a <= b of niet a <=b) zijn dus niet met lagere orde dan n log (n) te sorteren.

ontbinden in priemfactoren (nog) niet NP-volledig

Helemaal onderaan stond dat het ontbinden in priemfactoren NP-volledig is. Dat is nog niet aangetoond en wordt onwaarschijnlijk geacht, want het zou impliceren dat NP = co-NP. Ik heb daarvoor in de plaats maar sudoku opgenomen, dat is in elk geval breed bekend... Oliphaunt 15 feb 2007 13:05 (CET)