Сбалансированное дерево запросов, асимтотический анализ - PullRequest
Новая
       5

Сбалансированное дерево запросов, асимтотический анализ

2 голосов
/ 22 мая 2010

Ситуация следующая: -

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

Мы хотим получить числа в отсортированном порядке по O (nlog n) время с использованием только вставки и обхода в порядке.

Ответ на этот вопрос: - 

Sort()
  initialize(t)
  while(not EOF)
     read(x)
     insert(x,t);
  Traverse(t);

Теперь запрос состоит в том, если мы читаем элементы во времени«n», а затем обойти элементы за время «log n» (обход по порядку), а затем общее время для этого алгоритма (n + logn), по моему мнению. Пожалуйста, объясните, как работает этот алгоритм длярасчет времени .. Как он будет сортировать список в O (nlogn) времени ??

Спасибо.

1 Ответ

4 голосов
/ 22 мая 2010

Каждая вставка O(log n). Вы делаете n вставки, что дает n * O(log n) = O(n log n) асимптотическую сложность по времени. Обход дерева O(n), потому что есть n узлов. Это добавляет до O(n + n log n), что отличается от O(n log n) константой, поэтому окончательная асимптотическая сложность равна O(n log n) ..

и затем пройти элементы в «log n

Обход O(n), а не O(log n). Вставка O(log n), и вы делаете n таких вставок.

...