Блог

Главная - Вопросы по программированию - Вычисление сложности логарифма

Вычисление сложности логарифма

#algorithm #time-complexity #complexity-theory #logarithm

#алгоритм #временная сложность #теория сложности #логарифм

Вопрос:

Как известно, сложность вставки узла в дерево AVL заключается log(c) в том, что c это количество узлов внутри дерева. Я хочу вставить m узлов в дерево, чтобы сложность:

log(c) log(c 1) ... log(c m)

Любые идеи / предложения о том, как я могу решить эту проблему и получить Big-O?

Комментарии:

1. Что вы имеете в виду под complexity of the following этим ? Если это буквально дополнение, о котором вы говорите, похоже, что O(m)

2. почему O (m)? если c = 0, то его log(m!), который равен O(m * log(m))

3. Ваш вопрос либо вводит в заблуждение, либо упускает важные детали!

4. Пожалуйста, предоставьте больше контекста! Сложности вычисляются алгоритмом.

5. Спасибо! На мой взгляд, Big-O был O(NlogN) бы там, где N=m c

Ответ №1:

Предполагая, что c не является константой:

 log(c) log(c 1) ... log(c m) = log(c * (c 1) * .... * (c m))
                     = log((m c)!/c!)
                     = log((m c)!) - log(c!)
                     = O_theta((m c)log(m c)- clogc)

Но ради больших сложностей мы обычно приводим свободные границы: O(NlogN) где N=m c

Метки: