Нужна помощь в изучении времени бега

Question

В данный момент я готовлюсь к выпускному экзамену по курсу информатики. Один из вопросов, который будет задан, - это, скорее всего, вопрос о том, как объединить время выполнения, поэтому я приведу пример.

Мне было интересно, если бы я создал программу, которая предварительно обработала входные данные, используя сортировку вставками, а затем выполнил поиск значения "X" с помощью бинарного поиска, как бы я соединил время выполнения, чтобы найти лучшие, худшие и средние сложности времени для случая общая программа?

Например...

Сортировка вставки
Худший случай O(n^2)
Лучший случай O (n)
Средний случай O(n^2)

Бинарный поиск в худшем случае O (logn)
Лучший кейс O(1)
Средний случай O (logn)

В худшем случае это будет O(n^2 + logn), или это будет O(n^2), или ни то, ни другое?
Будет ли лучший случай O(n)?
Будет ли средний случай O(nlogn), O(n+logn), O(logn), O(n^2+logn) или ничего из этого?

Я склонен переосмысливать решения, поэтому, если я смогу получить какие-либо рекомендации по объединению времени выполнения, это будет очень цениться.

Большое спасибо.

Answer 1

Обычно вы не "комбинируете" (как в добавлении) время выполнения, чтобы определить общий класс эффективности, а выбираете тот, который занимает наибольшее время для каждого худшего, среднего и лучшего случая.

Так что, если вы собираетесь выполнить сортировку вставками, а затем выполнить двоичный поиск после, чтобы найти элемент X в массиве, наихудший случай - O(n^2), а лучший - O(n) - все из вставки сортировать, так как это занимает больше всего времени.

Answer 2

Основываясь на моем ограниченном исследовании (мы не достигли Амортизации, так что это может быть то, где у Джима все остальное правильно), но в основном вы просто выбираете, основываясь на том, кто медленнее всего использует алгоритм.

Кажется, это хорошая книга на тему "Алгоритмы" (мне не с чем сравнивать): http://www.amazon.com/Introduction-Algorithms-Third-Thomas-Cormen/dp/0262033844/ref= sr_1_1? т =UTF8& QID =1303528736& стер =8-1

Также у MIT есть полный курс по Алгоритмам на их сайте, вот ссылка для этого также! http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/

Я на самом деле нашел это полезным, он может не отвечать конкретно на ваш вопрос, но я думаю, что это поможет вам более уверенно увидеть некоторые темы, которые объясняются несколько раз.