Какова сложности времени этой функции?

Question

Это пример в записи моей лекции. Является ли эта функция с сложностью времени $ o (n log n) $?. Потому что худший случай - это функция else филиал и 2 вложенные петли со временной сложностью $ log n $ и $ n $, так что это $ o (n log n) $. Я прав?

int j = 3;
int k = j * n / 345;
if(k > 100){
    System.out.println("k: " + k);
}else{
    for(int i=1; i<n; i*=2){
        for(int j=0; j<i; j++){
            k++;
        }
    }
}

Answer 1

Сложность времени упомянутого алгоритма - $ o (1) $, потому что для $ k> 100 $ у вас есть постоянная операция (println), и вы знаете: $ j = 3, k = 3 cdot n / 345 Подразумевает 100 = 3 CDOT N / 345 подразумевает n = 11500 $, означает для $ n ge 11500 $ ваш алгоритм имеет постоянное время выполнения (также другая часть постоянна, потому что будет вызван только $ N <11500 $).

За то, чтобы быть более ясным, взглянуть на это вопрос.

Answer 2

РЕДАКТИРОВАТЬ: Как указал Саид Амири, это на самом деле $ O (1) $, так как для асимптотически больших $ n $ else Ветвь на самом деле не взят; а if Часть выполняется, что тривиально постоянное время. Остальная часть этого ответа, который я оставляю для справки, была бы правильной, если, например, условие было k < 100. Анкет Извините за смешивание.

Временная комплексность по сути будет в порядке, сколько раз, когда $ k $ увеличивается в вложенных for петля. Продолжается какое -то дополнительное вещество, но если вы думаете об этом, это просто игра с постоянными факторами. Сколько раз будет увеличена $ k $?

Когда $ i = 1 $, $ k $ увеличивается один раз. Когда $ i = 2 $, $ k $ увеличивается на два дополнительных раз. Когда $ i = x $, $ k $ увеличивается $ x $ дополнительные раз. Давайте теперь предположим, что $ n = 2^M + 1 $. Тогда последняя итерация внутренней петли вызовет k Чтобы быть увеличенным $ 2^M $ времени.

$ k $ увеличивается на общую сумму $ 1 + 2 + ... + 2^M $ Times, или $ 2^{(M + 1)} - 1 $. Напомним, что `$ n = 2^m + 1 $. Таким образом, $ n - 1 = 2^m $, и у нас есть, что $ k $ увеличивается 2 доллара США (n - 1) - 1 $ в общей сложности.

$ k $ увеличивается несколько раз, что является линейным в $ n $; Ergo, это все $ o (n) $.

Answer 3

Хотя комментарии о IF/Else Branches являются правильными, я бы сказал, что ответ o (log n). Причина в том, что

System.out.println("k: " + k);

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

Не уверен, была ли это хитростью, или нет ...

Answer 4

Посмотрим:

int j = 3; занимает постоянное время O (1).

int k = j * n / 345 берет некоторую функцию логарифма времени Дж а также не переменные

if (k > 100) занимает постоянное время O (1).

System.out.println("k: " + k); принимает функцию логарифмы на k

for (int i=1; i<n; i*=2) принимает функцию логарифмы на не, Θ (log (n)), если быть точным, потому что если Т это количество итераций этого для цикла, чем значение я может быть выражен как: i = 2^Т-1, если t = 1 в первой итерации, поэтому цикл продолжается до тех пор, пока 2^Т-1 <n, куда не не меняется.

В исчислении, если 2^Т-1 <n тогда T-1 <log₂(n)

И если T-1 <log₂(n) тогда t <log₂(n) +1

И если в каждой итерации, Т увеличивается на 1, мы видим, что это для цикла действительно требует θ (log (n)), Если сложность времени выполнения кода внутри этого для цикла является постоянной, то есть o (1), конечно!

Внутри этого для петли есть еще один для петли:

for (int j=0; j<i; j++) k++;

Давайте анализируем это:

k++; занимает постоянное время, т.е. o (1) время.

Так что интересно анализировать сложность времени работы внутренней для цикла.

Посмотрим:

Согласно коду этого внутреннего для цикла, кажется, что есть я Итерации в этом внутреннем петле, так что время работы Θ (i), не просто O (i), потому что это делаетне разорвать посередине, но помните, что я <n, из -за внешней петли, поэтому в начале он занимает 1 итерацию, когда i = 1, 2 итерации, когда i = 2, 4 итерации, когда i = 4, 8 итераций, когда i = 8... и т. Д., Потому что я удваивается в конце внешней петли в линии i*= 2, поэтому в целом выполнение составляет 1+2+4+8+... итерации но до того как i≥n Таким образом, максимально возможное количество итераций в этом внутреннем петле - это когда i = n-1 С точки зрения наихудшего случая, поэтому, если в последнем исполнении внутреннего для цикла он работал n-1 итерации, так что раньше он работал (N-1)/2 итерации, и до этого он бежал (N-1)/4 итерации, и до этого он бежал (N-1)/8 Итерации ... так что в общей сложности исполнение было:

n-1 + (n-1)/2 + (n-1)/4 + (n-1)/8 ... = (n-1) (1 + 1/2 + 1/4 + 1/8 ...) = (n-1) (2) = 2n-2 = θ (n)

Напомним, что 1 + 1/2 + 1/4 + 1/8...=2 хорошо известна сумма геометрической последовательности.

Напомним, что внешняя для цикла принимает θ (log (n))

И внутренний для цикла принимает θ (n).

И сложность времени бега Для петли внутри для петли это сложность времени выполнения внешней для петли, умноженной на сложность времени выполнения внутренней для цикла, поэтому требуется время выполнения θ (nlogn).

Таким образом, время выполнения этой функции Θ (nlogn).

Надеюсь, что это хорошо отвечает на ваш вопрос и научит вас, как анализировать сложность времени работы алгоритмов и функций.