История изменений

0) да.

1) нет. Если речь о доступе к элементу - зависит от того где этот элемент (кэш, рам, своп или вообще по сети шарится). Если речь идет об арифметике, зависит от того на конвейре ли операция. Модель вычислений, основанная на асимптотических оценках сложности алгоритмов, потеряла актуальность как только у компьютеров появилась память со сложной иерархией. Тем не менее про эту модель до сих пор лекции читают, статьи пишут и делают всякие глубокомысленные выводы, откуда нынешняя дискуссия и пошла. Сейчас вот roofline модель появилась, она значительно более адекватна, а все эти О(...) имеют лишь сугубо теоретический интерес как правило.

2) с точностью до п.1.

3) да, насколько я понимаю - не силен в реализации деревьев, их до черта видов есть. Но общий принцип такой.

4) не обязательно, зависит от реализации. Если тупо по битам делать то да, если оптимизировать то все те же log_2(n), при условии что дерево сбалансированно.

5)

... Так почему же они оба из твоих слов O(1)?

Потому что такое определение О(1)! Грубо, запись f(x) = O(g(x)) означает что f(x)<Cg(x), где С некоторая константа (хрен знает какая, важно что она существует). Если f(x) < C, то можно написать что f = O(1). Если при этом f<C g, то можно написать что f = O(g). И обе эти записи будут верными.

Я не шучу, там знак равенства это на самом деле не знак равенства а знак принадлежности к некоторому множеству.

Вот Вам небольшая иллюстрация - все (кто лекции не прогуливал), знают что сложность добавления элемента в список O(1), а в вектор O(N). ВОпрос, куда лучше набивать историю чего нить, в std::list<my_pod_type> или в std::vector<my_pod_type>? Где быстрее (в секундах) будет работать push_back()? При аллокаторах по умолчанию разумеется.

0) да.

1) нет. Если речь о доступе к элементу - зависит от того где этот элемент (кэш, рам, своп или вообще по сети шарится). Если речь идет об арифметике, зависит от того на конвейре ли операция. Модель вычислений, основанная на асимптотических оценках сложности алгоритмов, потеряла актуальность как только у компьютеров появилась память со сложной иерархией. Тем не менее про эту модель до сих пор лекции читают, статьи пишут и делают всякие глубокомысленные выводы, откуда нынешняя дискуссия и пошла. Сейчас вот roofline модель появилась, она значительно более адекватна, а все эти О(...) имеют лишь сугубо теоретический интерес как правило.

2) с точностью до п.1.

3) да, насколько я понимаю - не силен в реализации деревьев, их до черта видов есть. Но общий принцип такой.

4) не обязательно, зависит от реализации. Если тупо по битам делать то да, если оптимизировать то все те же log_2(n), при условии что дерево сбалансированно.

5)

... Так почему же они оба из твоих слов O(1)?

Потому что такое определение О(1)! Грубо, запись f(x) = O(g(x)) означает что f(x)<Cg(x), где С некоторая константа (хрен знает какая, важно что она существует). Если f(x) < C, то можно написать что f = O(1). Если при этом f<C g, то можно написать что f = O(g). И обе эти записи будут верными.

Я не шучу, там знак равенства это на самом деле не знак равенства а знак принадлежности к некоторому множеству.

Вот Вам небольшая иллюстрация - все (кто лекции не прогуливал), знают что сложность добавления элемента в список O(1), а в вектор O(N). ВОпрос, куда лучше набивать историю чего нить, в std::list<my_pod_type> или в std::vector<my_pod_type>? Где быстрее (в секундах) будет работать push_back()?