Время выполнения Big O для разных структур данных

Question

Я попытался определить время выполнения Big O следующих структур данных. Правильны ли они?

• Вставка n целых чисел в изначально пустое дерево AVL (в лучшем случае) O (log n)

• Вставка n целых чисел в изначально пустое дерево AVL (наихудший случай) O (log n)

• Вставка n целых чисел в изначально пустое двоичное дерево поиска, которое не приводит в исполнение свойства структуры (лучший вариант) O (log n)

• Вставка n целых чисел в изначально пустое двоичное дерево поиска, которое не приводит в исполнение свойства структуры (наихудший случай) О (п) * ** +1026 1025 *

Также было бы полезно объяснить, почему они неверны

Answer 1

Я предполагаю, что вам нужно общее время для вставки всех элементов:

(1) в в лучшем случае для дерева AVL , вам никогда не понадобится идти ниже корня, [т.е. все элементы равны корню], поэтому это будет O (n) . [никогда не нужно углублять больше, чем на 1 шаг, независимо от размера дерева]. O (1) на элемент.

(2) наихудший случай для дерева AVL : вставка n целых чисел в дерево AVL - это O (nlogn). каждый шаг - O (log (T)), где T - размер в этот момент. O(log1) + O (log2) + ... + O(logn) = O(log1 + log2 + ... + logn) = O(log(1*...*n)) = O(nlogn). поэтому O (nlogn) . O (logn) на элемент

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

(4) с без применения структуры, наихудший случай : как сказано в других ответах, для каждого элемента найдено место O (n), поэтому в целом сложность наименьшего времени будет O (N ^ 2) * * тысячу двадцать-пять. O (n) на элемент.

Answer 2

Это неверно в вашем определении:

Вставка n целых чисел в изначально пустое дерево AVL (в лучшем случае) O (log n)

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

Итак, мое предположениеявляется то, что вы даете правильный O() для одного элемента (это немного неправильно, потому что наилучшего можно достичь на специальных входных данных; ваши оценки среднего значения, а не лучшего), поэтому для общей описанной операции я умножу каждыйс O(n):

• Вставка n целых чисел в изначально пустое дерево AVL ( best case) O(n*log n) UPDATE: это среднее;лучшее время может быть меньше на специальных входах.

• Вставка n целых чисел в изначально пустое дерево AVL (наихудший случай) O(n*log n)

• Вставкаn целых чисел в изначально пустое двоичное дерево поиска, которое не обеспечивает свойства структуры (в лучшем случае) O(n*log n) UPDATE : это может зависеть от реализации и последовательности целых чисел;поэтому лучший случай - O(n) (см. комментарии).

• Вставка n целых чисел в изначально пустое двоичное дерево поиска, которое не обеспечивает свойства структуры (наихудший случай) O(n*n)

Answer 3

Извините, но все они не правы.

то, что вы использовали, это Big-Os для одной вставки. Если вы делаете n из них, вы должны взять это время n.

Итак, правильные цифры:

Вставка n целых чисел в:

• Дерево AVL (наихудший случай): O (log (n) * n)
• Дерево AVL (в лучшем случае): Это сложно, но я думаю, это O (log (n) * n) , тоже
• двоичное дерево поиска, которое не обеспечивает свойства структуры (в лучшем случае): O (n) - Наилучшее время вставки кейса для 1 элемента на самом деле O (1)
• двоичное дерево поиска, которое не обеспечивает свойства структуры (наихудший случай): O (n ^ 2) - если вы не применяете свойства структуры, вы можете получить полностью несбалансированное дерево, поэтому в худшем случае ваше дерево из n элементов имеет высоту n => ваше дерево превратится в список.

Answer 4

Как вставка целых чисел n может привести к большому O O(logn). Это не имеет никакого смысла. Конечно, чтение целых чисел займет не менее O(n).

Так что для несбалансированного, BST примера наихудший случай, когда вы вставляете отсортированный список чисел, например 1,2,3,4. Вставка 1 занимает 0 раз. Вставка 2 занимает ~1 раз. Вставка 3 занимает ~2 время. и т.д. Это составляет 1+2+3+...+n = O(n^2).

Аналогично, в лучшем случае каждая последующая вставка занимает log(i) время. Таким образом, общее время работы составляет log(1)+log(2)+log(3)+...+log(n). Что это оценивает, не сразу очевидно. Но если вы немного разбираетесь в исчислении, вы можете видеть, что это (почти) приближение правила трапеции к интегралу от log n от 1 до n. Это примерно nlogn - n = O(nlogn).

Я уверен, что вы можете сделать аналогичный анализ для деревьев AVL.

Answer 5

Да, вы правы, если вы умножаете все на n.Ваше время работы для одного элемента.