Что такое биг-тета следующего кода?[I * I <= n] - PullRequest
0 голосов
/ 11 октября 2018
for (k = 1; k <= n; k++)
   for (i = 1; i*i <= n; i++)
       // some O(1) operations`

Меня просят найти бета-тэту этого кода.Я вычислил i*i < n.Я могу переписать его как I < n/I.И, отслеживая это, я получил следующее:

I                # of interations
1               n
2               n/2
3               n/3
.                .
.                .
.                .
n/L              1

Хотя я не уверен, как отсюда идти.Должен ли я вычислить сумму n / i от i = 0 до n?В таком случае, как рассчитать сумму при наличии переменной (n)?

Я знаю, что, если я найду LI, найду необходимое количество итераций.И поскольку он заканчивается после L = N / L, я не могу вычислить L в терминах N.

Я очень смущен этим.Любое понимание будет оценено.

1 Ответ

0 голосов
/ 11 октября 2018

Внешний цикл имеет N итераций.Внутренний цикл имеет квадратные (N) итерации.Умножьте эти два, чтобы найти ответ.

...