Сложность времени для цикла

time-complexity

259 просмотра

2 ответа

Внешний цикл выполняется n раз, в то время как внутренний цикл выполняется? Таким образом, общее время n * что-то.

Нужно ли учить суммирование, если да, то какую книгу ссылаться?

for(int i=1;i<=n;i++) 
  for(int j=1;j<=n;j+=i)
    printf("*");
Автор: srbh Источник Размещён: 08.11.2019 11:14

Ответы (2)


0 плюса

Решение

Я считаю, что временная сложность такова O(n*log(n)). Вот почему:

Давайте выберем произвольное натуральное число i и посмотрим, сколько шагов внутренний цикл делает для этого, учитывая i. Хорошо для этого я, вы идете от j = 1 до j <= n с скачком i между ними. Итак, в основном вы делаете это суммирование много шагов:

summation =  1 + (1+i) + (1+2i) + ... (1+ki) 

где k - наибольшее целое число такое, что 1 + ki <= n. То есть, k - это количество шагов, и это то, что мы хотим решить. Ну, мы можем решить для k в равенстве, в результате k <= (n-1)/iи, таким образом k = ⌊(n-1)/i⌋. То есть k - это функция пола / целочисленное деление (n-1)/i. Поскольку мы имеем дело со сложностями времени, эта функция этажа не имеет значения, поэтому мы просто скажем k = n/iдля простоты. Это количество шагов, которые внутренний цикл предпримет для данного i. Таким образом, мы должны добавить все это для i = 1 к i <= n.

Итак, numsteps будет этим дополнением:

numsteps = n/1 + n/2 + n/3 + ... n/n
         = n(1 + 1/2 + 1/3 + ... 1+n)

Таким образом, нам нужно найти сумму 1 + 1/2 + ... 1 / n, чтобы закончить это. На самом деле нет хорошей закрытой формы для этой суммы, но она порядка ln(n). Вы можете прочитать больше об этом здесь . Вы также можете догадаться, так как integral from 1 to n of 1/x is ln(n). Опять же, поскольку мы имеем дело со сложностью времени, мы можем просто использовать ln (n) для представления его сложности. Таким образом, мы имеем:

numsteps = n(ln(n))

И так сложность времени есть O(n*log(n)).

Редактировать: мой плохой, я рассчитывал сумму: P

Автор: gowrath Размещён: 20.08.2016 12:45

4 плюса

К этому вопросу можно подойти путем осмотра:

n = 16

i  |  j values         | # terms
1  |  1, 2, ..., 16    | n
2  |  1, 3, 5, ..., 16 | n / 2
.. |  ..               | n / 3
16 |  16               | n / n

В приведенной выше таблице iприведено значение внешнего цикла, и j valuesпоказаны итерации внутреннего цикла. По проверке мы видим, что петли будут предпринимать n * (1 + 1/2 + 1/3 + ... + 1/n)шаги. Это ограниченная гармоническая серия. Как показано в этой статье Math Stack Exchange , для приведенного выше выражения в терминах нет закрытой формы n. Однако, как показано в этой статье , есть верхняя граница O(n*ln(n)).

Итак, время выполнения ваших двух циклов O(n*ln(n)).

Автор: Tim Biegeleisen Размещён: 20.08.2016 12:18
Вопросы из категории :
32x32