Какова временная сложность ниже геометрии c серии?

Question

1) .... + n / 16 + n / 8 + n / 4 + n / n .. =?

2) ... + n / 5 + n / 4 + n /3+n/2...n/n..=?

Я работаю над нахождением временной сложности нескольких алгоритмов, в которых я наткнулся на несколько геометрических рядов c. Я считаю, что 1-я серия геометрии c имеет log (n). Какова временная сложность 2-й серии геометрии c?

Answer 1

Предполагая, что (1) равно n * (… + 1/2 ^ k +… + 1/16 + 1/8 + 1/4 + 1/2 + 1/1), ответ равен 2n, потому что сумма 1 + 1/2 + 1/4 +… + 1/2 ^ k +… сходится к значению 2. Чтобы увидеть это:

1/1 + 1/2 + … + 1/2^n + … = k
(1/1 + 1/2 + … + 1/2^n + …)/2 = k/2
1/2 + 1/4 + … + 1/2^(n+1) + … = k/2
k - 1 = k/2
k/2 = 1
k = 2

Ключевым шагом выше было распознавание LHS третьей строки на единицу меньше, чем LHS первой строки.

Для (2) n * (… + 1 / k +… + 1/5 + 1/4 + 1/3 + 1/2 + 1 / 1) в n раз больше гармоник c серии. Серия гармоник c расходится, поэтому она не определена и стремится к бесконечности. Чтобы увидеть это, сравните две серии:

1/1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + …
1/1 + 1/2 + 1/4 + 1/4 + 1/8 + 1/8 + 1/8 + 1/8 + …

Второй такой же, как первый, но во всех терминах знаменатели были увеличены до следующей более высокой степени двух. Таким образом, вторая серия не может суммироваться с большим значением, чем первая. Но вторая серия явно расходится, так как мы можем сгруппировать две 1/4, четыре 1/8, et c., Чтобы получить сумму 1 + 1/2 + 1/2 +… + 1/2 +…

Answer 2

1) ... + н / 16 + н / 8 + н / 4 + н / н .. =? является серией геометрии c, и ее сумма всегда будет меньше 2n. Так что это O (n).

2) ... + n / 5 + n / 4 + n / 3 + n / 2 ... n / n .. =? представляет собой ряд гармоник c, сумма которого будет равна logn. Существуют математические вычисления для получения этого значения. Так что это O (log n)

Answer 3

1) n {(1/1) + (1/2) + (1/4) + (1/8) + ...} ==> O (n), потому что этот ряд {(1/1 ) + (1/2) + (1/4) + ...} равно числу 2

2) n {(1/1) + (1/2) + (1/3) + (1/4) + ...} ==> O (n Lnn), потому что этот ряд {(1/1) + (1/2) + (1/3) + ...} равен Lnn (это серия гармоник c)