Обозначение Big O и временная сложность фрагмента кода C ++ - PullRequest
Новая
       6

Обозначение Big O и временная сложность фрагмента кода C ++

0 голосов
/ 22 февраля 2019

Итак, я ищу подтверждение того, какова временная сложность фрагмента кода c ++: 

for(int i = 0; i<N, i++){
    for(int k = 1; k<N; k*=2){
    //code with O(1)
    }
 }

Я думаю, что это будет O(NlgN), где lg - база журнала 2. Внутренний цикл будетбыть O(lgN), так как k удваивается после каждой итерации.Внешний цикл явно O(N), что делает весь код: 

 O(N)*O(lgN) = O(NlgN).

1 Ответ

0 голосов
/ 22 февраля 2019

Да, это в O (n log n), но основание не имеет значения в больших обозначениях O, так как f=n \cdot log_2(n) \in \mathcal{O}(log_2(n) * n ) \subseteq \mathcal{O}(\frac{ln(n)}{ln(2)} * n ) \subseteq \mathcal{O}(log(n) * n ) \ni f = n \cdot ln (n) т.е.

enter image description here

Примечаниелог в конце должен все еще быть ln, но люди не заботятся о путанице с тем, когда лог составляет 10 или e, так как это не имеет значения в больших O.

Так что даже for(int k = 2; k<N; k*= k) будетбыть одинаковым по сложности при использовании больших обозначений O.Однако иногда люди записывают постоянные коэффициенты при сравнении очень незначительных оптимизаций, но это невозможно, если вы не говорите о реализации быстрой сортировки, которая выполняется на миллиардах экземпляров по всему миру.

Что касается того, как мы можем быть уверены, что ваш внутренний цикл на самом деле ограничен log(n) Я также не нашел хорошего математического доказательства.Конечно, выполнение этого является своего рода доказательством, но мой теоретический подход заключается в том, что мы можем согласиться, что внутренний цикл выполняется так часто, как вашей функции k *= 2 требуется больший аргумент для достижения n, поэтому где k(x) >= n и чтомы знаем, какой x нам нужен, чтобы получить k(x), который мы хотим, это обратная функция k^(-1), и обратные функции для 2^x равны log_2(x).

...