Стандартные контейнеры C++

Вроде все ассоциативные(map,set,multimap,multiset). Инфа из справочника.

std::dequeue и std::vector?

> std::dequeue и std::vector?

Только если отсортированы. binary_search

Я не пойму почему тут логарифм по основанию e. Во всех справочниках сложность алгоритмов вычислается с помощью логарифмов по основанию 2. Как сюда экспонента попала?

Сложность по порядку оценивают. Т.е. с точностью до величин меньших порядков малости и домножение на константы. Переход ln -> lg -> log2 - это, если мне ни с кем не изменяет память, домножение на константу.

Совсем ниче не понял. Есть причина тому что в основании 2. Потому как массив делится на 2 для поиска и потом каждая часть разбивается на 2 и так далее. Получается тепень двойки. Но причем тут степень экспоненты? Ткните где про это прочитать можно что ли.

Куда тыкать точно не знаю, но сложность всегда оценивается по порядку зависимости от размеров или еще чего-либо. Т.е. важен только порядок. Т.е. X ~ 10*X ~ 100*X !~ 0.000001*X*X, т.к. считается, что X->inf.

А переход к другому основанию логорифма - домножение на константу.

>...важен только порядок...

>А переход к другому основанию логорифма - домножение на константу.

Хех, домножив на константу можно и порядок сменить - смотря какая констатна.

На какую константу предлогаешь домножить N^2 чтобы получить N^3?

Может я чего не понимаю, но помоему тут весь тред обсуждался порядок возростания функции сложности алгоритма от N.