|
Тема |
Сложност на метод - big O() |
|
Автор | EroS (Нерегистриран) | |
Публикувано | 22.04.06 18:13 |
|
|
Здравейте, имам един въпрос: вчера имах изпит по информатика и триабваше да напишем следниа метод (а тожа и решението ми, доколкото помня, може и да не се компилира, но поне дава представа за какво става ан въпрос.)
/**
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-то на метода да ми каже. А и кой е най-лошия възможен случай?
|
| |
|
|
|