сложность pop, push и multipop

Question

Я немного путаюсь с расчетом стоимости поп и толчка в структурах данных.

1) Он говорит, толчок (х): реализация, как обычно, Θ (1) Время

Означает ли это, если один толчок операция выполняется Q (1) время, если 2 операции сделано, Θ (2), и если n операций push сделано Θ (n) раз?

2) MultiPOP (к): вызовы поп() до K раза, Θ (к) время наихудшего

Это как удалить K верхних объекты из стека S. Как Θ (к) приходит? поскольку k объектов выскочит, время будет Θ (k).

3) Это самая запутанная часть. Начать с пустых и выполнять m операций. Каково общее время?

не более m толкает, m pops: total O (m). Как это происходит O (m). Поскольку существует 2m операций, не нужно ли это O (2m).

Поэтому во время наихудшего случая это не должно быть O (2 м).

4) Вот еще одно заявление. Это слишком сложно ввести в заблуждение

Как насчет последовательности операций n PUSH, POP и MULTIPOP? Если стек изначально пуст, для случая MULTIPOP наихудшая операция - O (n).

Поэтому последовательность п операции может стоить O (N * N)

Может кто-то пожалуйста, объясните, как это происходит?

Answer 1

1. Если push имеет сложность O (1), это означает, что время работы меньше некоторой константы C> 0. Следовательно, для n операций время работы меньше nC, поэтому сложность O (n).
2. Multipop вызывает pop k раз, поскольку pop имеет сложность O (1), время работы мультиплета k O (1) = O (k).
3. O (2m) = O (m), поскольку константы не имеют значения при вычислении сложностей.
4. Худшая сложность случая - это O (n^2), так как многопроцессор имеет сложность O (n) и push/pop of O (1). Однако для последовательности операций часто используется Amortized Analysis, и в этом случае амортизированная сложность для последовательности push, pop и multipop равна O (n).