Поиск сложности заданного кода

Question

Я боюсь найти сложность заданного кода. Я думаю, что я борюсь с определением правильной сложности и тем, как на самом деле анализировать сложность. Код для анализа выглядит следующим образом:

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, то есть цикл в методе реорганизованного и doThings будет выполняться ровно один раз. Другая возможность заключается в том, когда i-й элемент массива равен 17, что означает, что цикл doThings не будет выполняться полностью на этой итерации. Таким образом, в обоих случаях лучший случай = Ο (n).

2) В худшем случае, когда число 17 находится в конце массива и когда число 17 не находится в массиве. Это будет означать, что массив будет пройден n × n раз, что означает, что наихудший случай будет равен Ο (n^2).

Может ли кто-нибудь помочь мне правильно ответить на вопросы, если мой неверен и, если возможно, объяснит проблему?

Answer 1

«лучший случай» массив пуст, и вы ничего не ищете.

Худший случай, что вы смотрите на каждый элемент, потому что никогда не видите 17. Все остальные случаи находятся между ними.

if (arr[i]==17){ является «самым горячим путем» кода, то есть он работает чаще всего.

Он всегда будет выполнять в общей сложности n*(n-1)/2 раз (я думаю, что я сделал, что математика справа) в худшем случае, потому что, даже если вы установили found = true, метод reorganize не знает об этом, не заканчивается, и продолжает для поиска, даже если вы уже просмотрели весь массив.

В принципе, сгладить код без методов. У вас есть этот вопрос.

What is the Big-O of a nested loop, where number of iterations in the inner loop is determined by the current iteration of the outer loop?