Амортизированная и средняя сложность выполнения

Question

Это не домашнее задание, я изучаю Амортизированный анализ. Меня что-то смущает. Я не могу полностью понять смысл между Амортизированной и Средней сложностью. Не уверен, что это правильно или нет. Вот вопрос:

-

Мы знаем, что во время выполнения сложность программы зависит от комбинации входных программ --- Пусть вероятность программы со сложностью выполнения О (п) р, где p < < 1, а в других случаях (т. е. для возможных случаев (1-p)), сложность выполнения равна O (logn). Если программа запускается с K комбинаций различных входных, где K является очень большое число, мы можем сказать, что амортизируется и среднее время выполнения сложность этой программы:

-

Первый вопрос: Я прочитали вопрос здесь: Difference between average case and amortized analysis

Итак, я думаю, что нет ответа на среднюю сложность выполнения. Потому что мы не знаем, какой средний вход. Но это, кажется, p * O (n) + (1-p) * O (logn). Что правильно и почему?

Во-вторых, амортизированная часть. Я прочитал Constant Amortized Time, и мы уже знаем, что Амортизированный анализ отличается от анализа в среднем случае тем, что вероятность не участвует; амортизированный анализ гарантирует среднюю производительность каждой операции в худшем случае.

Могу ли я просто сказать, что амортизированное время выполнения - O (n). Но ответ - O (p n). Я немного запутался в том, почему это связано с вероятностью. Хотя O (n) = O (p n), но я действительно не могу понять, почему p может появиться там? Я меняю образ мышления. Предположим, что мы потеряли время, тогда K становится очень большим, поэтому амортизированное время выполнения (K p O (n) + K * (1-p) O (logn))/k = O (p n). Кажется, это та же идея со средним случаем.

Извините, что смутитесь, помогите мне, пожалуйста, сначала!

Answer 1

С «средней» или «ожидаемой» сложностью вы делаете предположения о распределении вероятности проблемы. Если вам не повезло (или если ваш генератор проблем злонамеренно не соответствует вашему предположению 8 ^), все ваши операции будут очень дорогими, и ваша программа может занять гораздо больше времени, чем вы ожидаете.

Амортизационная сложность является гарантия на общую стоимость любой последовательности операций. Это означает, что независимо от того, насколько вреден ваш генератор проблем, вам не нужно беспокоиться о последовательности операций, занимающих гораздо больше времени, чем вы ожидаете.

(В зависимости от алгоритма нетрудно случайно наткнуться на наихудший случай. Классическим примером является наивный Quicksort, который очень сильно влияет на преимущественно отсортированный вход, хотя «средний» случай выполняется быстро)