это не домашнее задание, я изучаю амортизированный анализ. Что-то меня смущает. Я не могу полностью понять значение между Амортизированной и Средней сложностью. Не уверен, что это правильно или нет. Вот вопрос:
--
Мы знаем, что сложность выполнения программы зависит от комбинаций входных данных программы --- Предположим, что вероятность программы со сложностью выполнения O (n) равна p, где p ‹* 1, а в других случаях (например, для (1 -p) возможные случаи), сложность выполнения - O (logn). Если мы запускаем программу с K различными входными комбинациями, где K - очень большое число, мы можем сказать, что амортизированная и средняя сложность выполнения этой программы составляет:
--
Первый вопрос: я прочитал вопрос здесь: Разница между средним случаем и амортизированным анализом
Итак, я думаю, что нет ответа на средний уровень сложности выполнения. Потому что мы не знаем, какой средний ввод. Но это похоже на p * O (n) + (1-p) * O (logn). Что правильно и почему?
Во-вторых, амортизируемая часть. Я прочитал Постоянное амортизированное время, и мы уже знаем, что амортизированный анализ отличается от анализа среднего случая тем, что вероятность не задействована; Амортизированный анализ гарантирует среднюю производительность каждой операции в худшем случае.
Могу я просто сказать, что амортизированное время выполнения - 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). Вроде бы та же идея со средним корпусом.
Извините за путаницу, помогите, пожалуйста, сначала спасибо!
