Нахождение сложности данного кода
Я борюсь, чтобы найти сложность данного кода. Я думаю, что я борюсь с определением правильной сложности и как на самом деле анализировать сложность. Код для анализа выглядит следующим образом:
public void doThings(int[] arr, int start){
boolean found = false;
int i = start;
while ((found != true) && (i<arr.length)){
i++;
if (arr[i]==17){
found=true;
}
}
}
public void reorganize(int[] arr){
for (int i=0; i<arr.length; i++){
doThings(arr, i);
}
}
Вопросы:
1) Какова сложность случая реорганизации в лучшем случае и для каких входов это происходит?
2) Какова сложность наихудшего случая метода реорганизации и для каких входов это происходит?
Мои ответы:
1) Для метода реорганизации возможны два лучших варианта. Во-первых, когда длина массива равна 1, это означает, что цикл в методе reorganize и doThings будет запущен ровно один раз. Другая возможность - это когда i-й элемент массива равен 17, что означает, что цикл doThings не будет полностью выполняться на этой i-й итерации. Таким образом, в обоих случаях лучший случай = Ο (n).
2) Наихудший случай был бы, когда число 17 находится в конце массива и когда число 17 отсутствует в массиве. Это будет означать, что массив будет пересмотрен n×n раз, а это означает, что наихудший случай будет Ο(n^2).
Может ли кто-нибудь помочь мне правильно ответить на вопросы, если мои вопросы неверны и, если возможно, объяснить проблему?
1 ответ
В "лучшем случае" массив пуст, и вы ничего не ищете.
В худшем случае вы смотрите на каждый элемент, потому что никогда не видите 17. Все остальные случаи находятся между ними.
if (arr[i]==17){ это "самый горячий путь" кода, то есть он запускается чаще всего.
Это всегда будет выполнять в общей сложности n*(n-1)/2 раз (я думаю, что я сделал эту математику правильно) в худшем случае, потому что даже когда вы установите found = true, reorganize Метод не знает об этом, не заканчивается и продолжает поиск, даже если вы уже отсканировали весь массив.
По сути, выровнять код без методов. У вас есть этот вопрос.