Асимптотический анализ заданного кода - PullRequest
Новая
       29

Асимптотический анализ заданного кода

0 голосов
/ 24 мая 2018

Мне дали следующий псевдокод: 

 j = 1
 while j < n:
      k = 2
      while k < n:
           k = k*k
      j++

В моем представлении этот фрагмент псевдокода имел бы следующую сложность: 

 O(n*log(n))

Поскольку внешний цикл выполняет nраз.В то время как внутренний цикл по сути делит шаг приращения пополам каждый раз.Неужели мои мысли слишком далеки?

edit: еще 1 (это не домашние задания, я обещаю, просто примеры для понимания) 

 for i = 1 to n:
    for j = 1 to n:
       k = j*j
       while k < n:
          k++

В этом случае будет выполнен самый внешний циклп раз.Средний цикл также будет выполнен n раз, теперь мы будем n 2 раз.Внутренний цикл, как я понимаю, будет выполнять log (n) раз, что приводит нас к O (n 2 * log (n)) разам.Правильно ли мое понимание?

Ответы [ 3 ]

0 голосов
/ 24 мая 2018

Да, вы были бы правы, первый цикл прямо как O (n).Вторая часть немного сложнее.Я собираюсь использовать разум, а не строгость, чтобы показать его O (logn).

Итак, давайте на секунду предположим, что k = k * 2.Это знакомая последовательность, которую мы знаем как O(logn), однако мы видим, что k >= 2 для любого заданного цикла, поэтому мы знаем, что последовательность k = k*k будет ограничена сверху O(logn), то есть она равна большинству O (logn).Легко видеть, что это не O(1), поэтому мы знаем, что O (1) является нижней границей.Возьми это вместе, чтобы получить O(nlogn)

0 голосов
/ 24 мая 2018 
O(n log(n))

k ^ log (n) - это именно то значение, где k будет равно или больше n.

log (n) = x означает 2 ^ x = n

вы запускаете цикл n раз.

, поэтому сложность составляет O (n * log (n))

0 голосов
/ 24 мая 2018

Это O (n log log n).

Внешний цикл просто повторяет внутренний цикл n раз, что касается времени, поэтому он дает множитель n.

.Внутренний цикл сложнее, он повторяет квадрат k.Посмотрите, как это происходит: 2^1 -> 2^2 -> 2^4 -> 2^8 -> 2^16 -> 2^32 -> ... Так, например, если n = 2^32, цикл будет иметь 5 итераций.Здесь log_2 (n) равно 32, а log_2 (32) равно 5.

Обычно, если n = 2^(2^r), внутренний цикл достигнет n после r итераций.Взяв логарифм, мы приходим к log n = 2^r.Взяв логарифм в другой раз, мы получим log log n = r.Как вы, вероятно, знаете, основа логарифма не важна при работе с асимптотическим поведением, если она постоянна.

Итак, у нас есть n итераций цикла, который сам делает log log n итераций, делая общую сложность O (n log log n).

...