Анализ Big-O - While Loops

Мне была задана проблема программирования, которая задала массив, определить, является ли это обходным порядком двоичного дерева. Мое решение заключается в следующем:Анализ Big-O - While Loops

public static boolean isPostOrder(int[] array) { 

    int root = array[array.length - 1]; 

    int i = 0; 

    while(array[i] < root) { 
     i++; 
    } 

    while(array[i] > root) { 
     i++; 
    } 

    return i == array.length - 1; 

}

Я пытаюсь понять, Big O. Я прочитал этот учебник:

What is a plain English explanation of "Big O" notation?

Однако я до сих пор путают о сложении и петель в то время. Я предполагаю, что в этом случае мои циклы while O (1), так как мы просто сравниваем значение в массиве с целым числом, или я ошибаюсь?

Теперь добавление также O (1), потому что мы просто добавляем 1 к некоторому целому числу 1, правильно?

Таким образом, это решение O (1) или я что-то упускаю?

источник

2014-10-31 Sameer

O (1) - * постоянный * время доступа. Вы повторяете, нет? –

Стандартный цикл while, который вы представили, считается O (n). Добавление O (1). Если вы что-то делаете один раз, это O (1). Если вы делаете что-то 'n' раз, это O (n). – Compass

Ах ладно. Я также понял, что мое решение проблемы также неверно. Благодаря! – Sameer

Алгоритм выполнения имеет соединение с линейным соединением с размером ввода, потому что вы выполняете элементы входного массива. Это делает так, что ваш алгоритм O (n). Если бы у вас не было никаких циклов, это было бы O (1) = постоянное время доступа.

источник

2014-10-31 18:11:58 Joren

Основная идея нотации Big-O состоит в том, чтобы оценить количество основных операций, которые выполняет ваш алгоритм, и как влияет размер ввода.

Здесь ваша основная операция - увеличить i (++i). Вы повторяете массив размером N, и в худшем случае вы переходите все это. Таким образом, этот алгоритм имеет сложность O (N).

источник

2014-10-31 18:13:17 Mureinik

Анализ Big-O - While Loops

ответ

Смежные вопросы