Здравейте, имам един въпрос: вчера имах изпит по информатика и триабваше да напишем следниа метод (а тожа и решението ми, доколкото помня, може и да не се компилира, но поне дава представа за какво става ан въпрос.)

/**
Returns the number of the common elements of the two arrays.
@param a an array of int
@pre. a[] is sorted
@param b another array of int
@pre. b[] is sorted
@return the number of the common elements of the two arrays
*/
public static int common(int[] a, int[] b)
{
int common = 0;
int counterA = 0;
int counterB = 0;
while(counterA < a.length && counterB < b.length)
{
if (a[counterA] == b[counterB]
{
common++;
counterA++;
counterB++;
}
else if ( a[counterA] > b[counterB])
counterB++;
else
counterA++;
}
return common;
}

Това беше едната част от задачата, с която мисля че се справих, втората част - напишете сложността (complexity) на метода, използвайки "big-O notation". (Незнам как е на български).

Та моля ако някой знае какво е complexity-то на метода да ми каже. А и кой е най-лошия възможен случай?

1) n=100;
2) sum=0;
3) for(i=0;i<n;i++)
4) for(j=0;j<n;j++)
5) sum++

А) Редове 1 и 2 има статична инициализация, която отнема константно време а
Б) Операциите i=0 и i++ както и за проверката i<n представлява константен брой инструкции към процесора, което означаваме с b, c и d
В) Времената необходими за операциите j=0,j<n и j++ означаваме с e,f и g
Г) Операцията на ред 5 също изисква константно време h
Taka общото време на работа на програмата, за произволна стойност на n:
a+b+n.c+n.d+n(e+n.f+n.g+n.h)=n2.(f+g+h)+n.(c+d+e)+a+b
тъй като a,b,c,d,e,f,g,h са константи
Полагаме: i=f+g+h
j=c+d+e
k=a+b
Taka алгоритъма се изпълнява за време i.n2+j.n+k
Константите i j k не са определящи за бързодеиствието на алгоритъма и можем да ги пренебрегнем. Можем дори да пренебрегнем и j.n +k и да оставим единствено тази част с най високата степен.Тя е най значимата характеристика за този алгоритъм, защото от нея в най-голяма степен зависи времето за изпълнение, тъй като нараства най- бързо когато се увеличаваразмера на входните данни

Оттук следва, че за сложността на този алгоритъм може да приемем n2 (чете се "n-квадрат") или ако приемем означението голямо "О" можем да кажем, че сложността е О(n2)

Тези неща ги разбрах, повечето ги знаех, но мерси все пак. Та в случая на мойто решение, трябва ли да увеличавам на всяко сравнение ( == или < ) или само на всяко въртене на цикъла?

Аз пък го гледам че е О(N). Къде ги видя тези два вложени for-a?
3) for(i=0;i<n;i++)
4) for(j=0;j<n;j++)

извинявам се, забравил съм точка и запетайка след sum;

В случава ня твоето решение редът на нарастване (терминът на английски е ORDER OF GROWTH, няма да е зле някой който е запознат с БГ литературата по случая да каже КАК точно е преведен на БГ) е

О(min({a.length, b.length}))

надявам се с помощта на първия отговор по темата да може да си обясниш защо :)

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

Редактирано от id на 03.05.06 18:53.

Mersi mnogo. A koi e nai-loshiat slu4ai (worst case scenario)??? Kakvi triabva da sa masivite?

Целият смисъл на 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.

Mersi, sega ve4e mi stana iasno vsi4ko.

Po princip, nai-dobria algoritum za sortirane na masivi e s O(nlogn) (log e s osnova 2) - mai se narichashe merge sort, ako dobre si spomniam. A insertion sort-a e n^2.

Pak mersi!

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

алгоритъмът се казва radix sort.

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