сложность времени для списка stl с сортировкой в ​​цикле while

Question

Что такое сложность времени для следующего кода:

while(!list.empty()) {
    list.sort();
    a = list.front();
    list.pop_front(); 
    b = list.front();
    list.pop_front();
    /** do something calculations*/
}

Answer 1

Каждый вызов list.sort() имеет сложность O (N log N) ¹ .Это может быть быстрее для отсортированного списка, но с другой стороны, это также может быть медленнее (стандарт не гарантирует ничего в любом направлении для этого случая).Обычно он реализуется как сортировка слиянием, которая обычно не сильно (если вообще) влияет на существующий порядок.

В этом случае вы вызываете его O (N) раз, так что ваш общийсложность O (N ² log N).

Как уже отмечалось в комментариях, до тех пор, пока вы удаляете только элементы из начала списка, список останется отсортированным, поэтомунет необходимости повторной сортировки на каждой итерации.

Кроме того, я бы отметил, что если вы удаляете только элементы с самого начала, вы можете рассмотреть возможность использования std::deque вместо std::list.Несмотря на то, что в любом случае вы получите ту же вычислительную сложность, есть большая вероятность того, что вы заметите существенное улучшение реальной скорости, переходя с list на deque.Возможно, вам не удастся заменить deque на list в вашем случае (например, deque не обеспечивает такую ​​же стабильность итератора, как list), но в некоторых случаях это может быть сделано.

---

1. В случае необходимости точная формулировка из стандарта (§ [list.ops] / 32): « Сложность : Приблизительно N log N сравнений, где N == size(). "