Поиск Большой O гармонической серии

Ответ 1

Это легко следует из простого факта в Исчислении:

и имеет место следующее неравенство:

Здесь мы можем заключить, что S = 1 + 1/2 +... + 1/n является как Ω (log (n)), так и O (log (n)), таким образом, это Ɵ (log (n)), граница действительно плотная.

Ответ 2

Здесь формулировка с использованием дискретной математики:

Итак, H (n) = O (log n)

Ответ 3

Вопрос
1 + 1/2 + 1/3 +... + 1/n
Предположим, что n = 2 ^ k

• Если член 3rd имеет значение 1/3 и не 1/4 (1/2^2), это означает, что во всех существует n терминов, поэтому он будет O (n). Верно, что их sum может быть log n, но сложность - это количество итераций, а не сумма рядов.

• Рассмотрите его программно. Вы закончите цикл с 1 до n раз и добавив 1/n к сумме. Сколько раз это выполнялось???? 1 to n O (n)

• Если проблема была изменена на 1 + 1/2 + 1/4 + ... + 1/n, ряды теперь могут быть записаны как 1/2 ^ 0 + 1/2 ^ 1 + 1/2 ^ 2 +... + 1/2 ^ (k). Теперь подсказка, предоставленная вашим учителем, также имеет смысл. Сколько раз цикл будет работать??? 0 to k = k + 1 times, и из обоих серий мы можем видеть 2^k = n, следовательно, k = log (n). Таким образом, количество раз, когда оно выполнялось = log(n) + 1 = O(log n)

• Я думаю, вы или ваш учитель сделали опечатку.

Update

Как указал Дюкелинг, я, конечно, предполагаю, что the provided function is pseudo-code and calculating the time complexity of that. Теперь через год я понимаю, почему я получил смешанные голоса за этот конкретный ответ. Ребята это stackoverflow и предназначен в основном для кодирования. Если у вас есть проблемы, не связанные непосредственно с программированием, вы должны использовать другой сайт stackexchange, например https://math.stackexchange.com/