Вопрос о выступлениях Big (O)

Question

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

Метод get для ArrayList - O (1), а метод get для TreeMap - o (log n)

Теперь, если я сделал цикл, который перебирает весь список или дерево, например

for (int i = 0; i < blahblah.size(); i++)
{

blah blah

}

Для arraylist, будет ли эта производительность цикла o (1) или o (n)? Я понимаю, что когда вы извлекаете 1 элемент, производительность равна O (1), но этот цикл проходит по всему списку, поэтому не будет ли 1 * n элементов, что сделает его n?

То же самое с древовидной картой: o (log n) или n log n, поскольку вы проходите все дерево.

Answer 1

"Метод get для ArrayList - O (1), а метод get для TreeMap - o (log n)"

Причина, по которой ArrayList.get () - O (1), заключается в том, что поискИндекс просто смещение от источника.Неважно, имеет ли массив 5 или 5M элементов, это тот же объем работы.

TreeMap.get () - это O (log n), потому что может потребоваться пройти несколько элементов вниз по двоичному дереву.

Answer 2

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

Так что да, результатом будет O (n) или O (n log n), но в зависимости от структуры данных вы можете добиться большего. Рассмотрим связанный список - вместо O (n * n) вы можете просто отлично работать с O (n).

Но тогда есть нечто большее, чем просто большие O - константы действительно имеют значение в реальности. Одним из примеров может служить радикальная сортировка 32-битных чисел. O (n) для сортировки звучит великолепно, но быстрая сортировка, скорее всего, все равно будет быстрее для большинства разумных входных размеров.

Answer 3

Обход всех элементов будет O(n), так как вам нужно будет посетить каждый из них хотя бы один раз.

Древовидная карта должна быть O(n) также по той же причине, что и в отношении того, посещаете ли вы узлы в порядке пост-заказа, заказа или заказа.

Answer 4

Да, это будет O (n). Значения O почти всегда являются наихудшими.