Что на самом деле означает Логн? - PullRequest
Новая
       37

Что на самом деле означает Логн?

5 голосов
/ 01 мая 2011

Я просто учусь на уроке по Алгоритмам и перебираю QuickSort. Я понимаю алгоритм и то, как он работает, но не знаю, как получить количество выполненных им сравнений или то, что фактически означает logn, в конце дня.

Я понимаю основы, в пределах: 

x=logb(Y) then
b^x = Y

Но что это значит с точки зрения производительности алгоритма? Это число сравнений, которое вам нужно сделать, я понимаю, что ... вся идея кажется просто неразборчивой. Например, для быстрой сортировки каждый вызов уровня K включает 2^k вызовов, каждый из которых включает подсписки длиной n/2^K.

Итак, суммируем, чтобы найти количество сравнений: 

log n
Σ 2^k. 2(n/2^k) = 2n(1+logn)
k=0

Почему мы подводим итоги? Откуда взялся 2n (1 + logn)? Извините за неопределенность моих описаний, я просто так растерялся.

Ответы [ 5 ]

4 голосов
/ 01 мая 2011

Если вы рассматриваете полное сбалансированное бинарное дерево, то слой за слоем у вас есть 1 + 2 + 4 + 8 + ... вершин.Если общее количество вершин в дереве равно 2 ^ n - 1, то у вас есть 1 + 2 + 4 + 8 + ... + 2 ^ (n-1) вершин, считая слой за слоем.Теперь пусть N = 2 ^ n (размер дерева), тогда высота дерева равна n, а n = log2 (N) (высота дерева).Вот что означает log (n) в этих выражениях Big O.

1 голос
/ 13 января 2013

1 забудь про б-деревья на секунду

здесь 'математика: log2 N = k - это то же самое 2 ^ k = N .. это определение log , это может быть натуральное логарифмическое число (e) N = k aka e ^ k = n ,, или десятичное логарифмическое число 10 N = k равно 10 ^ k = n

2 см идеальное, сбалансированное дерево

1
1+ 1 1 + 1 + 1+ 1 8 из них 16 из них и т.д.

сколько элементов? 1 + 2 + 4 + 8..etc, так что для b-дерева 2 уровня есть 2 ^ 2-1 элемента, для дерева 3 уровня 2 ^ 3-1 и т. Д. ТАК ЧТО ТАКОЕ ВОЛШЕБНАЯ ФОРМУЛА: N_TREE_ELEMENTS = количество уровней OF ^ 2 -1, или используя определение log: log2 число уровней OF = number_of_tree_elements (можно забыть о -1)

3 Допустим, есть задача найти элемент в N-элементах b-tree, w / K level (aka height)

где построено b-дерево log2 height = number_of_tree elements

САМОЕ ВАЖНОЕ

так что в зависимости от того, как построено b-дерево, вам не нужно больше, чем «высота» ОПЕРАЦИЙ, чтобы найти элемент во всех N элементах, или меньше .. поэтому ЧТО ТАКОЕ ВЫСОТА равна: log2 number_of_tree_elements ..

так что вам нужно log2 N_number_of_tree_elements .. или log (N) для более короткого

1 голос
/ 01 мая 2011

ниже - образец дерева: 

      1
    /   \ 
   2     3
  / \   / \
 4   5 6   7

количество узлов в дереве равно 7, но максимум дерева равен log 7 = 3, журнал приходит, когда у вас есть методы деления и завоевания, при быстрой сортировке вы делите список на 2 подсписка, и продолжаете это, пока богатые маленькие списки, деления не занимают logn время (в среднем случае), поскольку максимум деления равен log n, разбиение на каждом уровне занимает O (n), потому что на каждом среднем уровне вы делите N чисел (может быть, список слишком велик для разбиение на разделы, но среднее число чисел на каждом уровне равно N, фактически некоторые из списков N). Так что для простого наблюдения, если у вас сбалансированное дерево разделов, у вас есть log n время для разбиения, что означает максимум дерева.

0 голосов
/ 02 мая 2011

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

0 голосов
/ 01 мая 2011

Чтобы понять, что означает O (log (n)), вы можете прочитать Big O notaion . В итоге это означает, что если ваш набор данных увеличится в 1024 раза, время выполнения будет только в 10 раз больше (или меньше) (для базы 2).

MergeSort работает в O (n * log (n)), что означает, что это займет 10 240 раз дольше. Bubble sort выполняется в O (n ^ 2), что означает, что это займет 1024 ^ 2 = 1 048 576 раз дольше. Так что на самом деле есть время, чтобы безопасно:)

Чтобы понять вашу сумму, вы должны посмотреть на алгоритм слияния в виде дерева: 

         sort(3,1,2,4)
        /            \
   sort(3,1)      sort(2,4)
    /     \        /     \
sort(3) sort(1) sort(2) sort(4)

Сумма повторяется по каждому уровню дерева. k = 0 - вершина, k = log (n) - нижняя часть. Дерево всегда будет иметь высоту log2 (n) (так как это сбалансированное двоичное дерево ).

Чтобы немного подсчитать: 

Σ 2^k * 2(n/2^k) = 
2 * Σ 2^k * (n/2^k) =
2 * Σ n*2^k/2^k = 
2 * Σ n = 
2 * n * (1+log(n)) //As there are log(n)+1 steps from 0 to log(n) inclusive

Это, конечно, много работы, особенно если у вас есть более сложные алгоритмы. В таких ситуациях вы по-настоящему счастливы за Основную теорему , но на данный момент она может просто запутать вас. Это очень теоретически, так что не волнуйтесь, если не поймете это сразу.

...