Что на самом деле означает «постоянная» сложность? Время? Количество копий / ходов? [closed]

В настоящее время этот вопрос не подходит для нашего формата вопросов и ответов. Мы ожидаем ответы должны быть подкреплены фактами, ссылками или опытом, но этот вопрос, скорее всего, потребует дебатов, аргументов, опросов или расширенного обсуждения. Если вы чувствуете, что этот вопрос можно улучшить и, возможно, снова открыть, посетите справочный центр для руководства.

Закрыт 7 лет назад .

Я могу вспомнить три операции в C ++, которые в некотором смысле можно описать как имеющие «постоянную» сложность. Я видел некоторые дискуссии ( *) относительно того, что это означает, и мне кажется, что мы могли бы просто сказать «все эти операции постоянны, но некоторые более постоянны, чем другие»: -)

( Edit 2 : Если вы уже думаете, что знаете ответ, пожалуйста, прочтите некоторые дискуссии по этому вопросу, прежде чем торопиться слишком рано: Какая именно структура данных является deques в C + +? Многие люди с довольно высокими оценками спорят о том, что означает «постоянный». Мой вопрос не так очевиден, как вы могли бы подумать!)

( Правка : Мне не нужно разбираться в том, что такое «сложность».Я хочу получить четкий ответ, возможно, с цитатами из стандарта C ++, который сообщает нам в точности , что должно быть константой . Такты процессора, реальное время или что-то еще? В отношении других потоков некоторые люди утверждали, что время совершенно не имеет отношения к тому, что требуется стандартом C ++.)

Применяются ли эти гарантии сложности в стандарте к среде выполнения операция? Или они просто указывают (максимальное) количество копий / ходов, которые могут произойти с содержащимися объектами? А что именно означает «амортизировано»?

1. Для (непустого) вектора v очевидно следующее во время выполнения:

swap(v.front(), v.back());

(хотя педант может указать, что это зависит от того, находятся ли данные в кешировать или выгружать или что-то еще!).

2. Для list l выполнение push_back несложно. Выделяется ровно один новый элемент, и несколько указателей в связанном списке перемешиваются. Каждый push_front включает одно выделение, всегда одного и того же объема памяти, так что это явно достаточно «постоянный». Но, конечно, время, необходимое для распределения, может быть весьма различным. Управлению памятью может потребоваться много времени, чтобы найти подходящую свободную память.

3. Но выполнение push_back для вектора еще более непредсказуемо. В большинстве случаев это будет очень быстро, но время от времени ему придется перераспределять пространство для всех данных и копировать каждый элемент в новое место.Таким образом, он менее предсказуем с точки зрения времени выполнения, чем один list :: push_front , но он по-прежнему называется постоянным (амортизируемым). В среднем добавление большого количества данных в вектор потребует сложности, не зависящей от добавляемого количества, и поэтому это называется «амортизированным постоянным» временем. (Я прав?)

И, наконец, я спросил о int , чтобы избежать сложностей, связанных с наличием другого типа. Например,a vector > может быть немного сложнее для рассуждений, потому что каждый элемент вектора (векторов) может иметь разный размер и, например, замена двух элементов не совсем так константа, как в случае 1. выше. Но в идеале мы могли бы ответить для всех vector , а не только для T = int .

(*) Пример дебатов см. В комментариях к этим ответам: Какая именно структура данных представляет собой deques в C ++?

задан Community 23 May 2017 в 10:30

0 ответов

Другие вопросы по тегам:

c++ complexity-theory time-complexity

Что на самом деле означает «постоянная» сложность? Время? Количество копий / ходов? [closed]

0 ответов

Похожие вопросы: