Целият смисъл на O нотацията е да намериш горна граница на даден алгоритъм, за да прецениш кой е най-лошия случай, до който може да се стигне...

по дефиниция f(n) E O(g(n)) означава, че за всяка начална точка в реда на естествените числа (n0) [ен нула], може да намериш константи c1, c2 > 0, такива че 0 <= f(n) <= c2g(n)място.

В твоя случай може да пообобщим нещата, защото min({a.length, b.lenght}) е освен горна и долна граница на функцията, т.е. най-общо казано f(n), т.е. времето за изпълнение ти е от вида f(x) = cn + a...

в твоя случай алгоритъмът ти по никакъв начин не зависи от подредбата на масивите, така че и в най-добрия и в най-лошия случай е... едно и също...

cn+ a

нито c, нито a се афектират по някакъв начин от масивите...

алгоритъмът ти е ефикасен защото използваш като предпоставка това, че масивите ти са подадени вече сортирани. ако не е така вероятно (wild guess) най-добрият случай ще бъде n, а най-лошият n^2, за справка - погледи анализа на insertion sort.

Съдържаниет е скрито
Влезте за да го видите

Редактирано от id на 04.05.06 00:24.