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

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?ie=UTF8&qid=1303528736&sr=8-1

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

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