Ошибка в использовании асимптотической записи

Я пытаюсь понять, что не так со следующим доказательством следующего повторения

Документация говорит, что это неправильно из-за индуктивной гипотезы, что Чего мне не хватает?

Допустим, конечная цель - доказать . Вы начинаете с гипотезы индукции:$T(n) = \mathcal{O}(n)$

i < $T(i) \leq ci$ для всех .$i < n$

И чтобы завершить доказательство, вы должны показать, что .$T(n) \leq cn$

Однако, что вы можете сделать вывод, так это , что бесполезно для завершения доказательства; вам нужна одна константа для (почти) всех . Следовательно, мы не можем ничего сделать, и не доказано.c n T ( n ) = O ( n $T(n) \leq (c+1)n$$c$$n$$T(n) = \mathcal{O}(n)$

Обратите внимание, что вы запутались между результатом и процессом доказательства. И еще один момент, на самом деле в этом случае, поэтому вы можете рассмотреть соответствующую гипотезу индукции, чтобы иметь возможность доказать это.Θ ( n log n $T(n)$$\Theta(n \log n)$

Вы пропустили несколько шагов. Похоже, вы пытаетесь по индукции доказать, что , и ваше доказательство выглядит так :$T(n) = O(n)$

Предположим, что при k < n . Это означает, что T ( k ) ≤ $T(k) = O(k)$$k<n$ для некоторых с . Тогда T ( n ) = 2 T ( ⌊ n / 2 ⌋ ) + n ≤ 2 c ⌊ n / 2 ⌋ + n ≤ ( c + 1 $T(k) \le c \, k$$c$ , поэтому T ( n ) = O ( n ) .$T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$$T(n) = O(n)$

Это доказательство с самого начала неверно: « для k < n » не имеет смысла. Big oh является асимптотическим понятием: T ( k ) = O ( k ) означает, что существует некоторая постоянная c и порог N такой, что ∀ k ≥ N , T ( k ) ≤ $T(k) = O(k)$$k \lt n$$T(k) = O(k)$$c$ . И снова, в конце, вы не можете сделать вывод, что « T ( n ) = O ( n ) », потому что это что-то говорит о функции T в целом, и вы только что-то доказали о конкретном значении T ( n ) ,$\forall k \ge N, T(k) \le c \, k$$T(n)=O(n)$$T$$T(n)$

Вы должны четко указать, что означает Так что, возможно, ваше доказательство идет:$O$

Предположим, что для всех k < n . Тогда T ( n ) = 2 T ( ⌊ n / 2 ⌋ ) + n ≤ 2 c ⌊ n / 2 ⌋ + n ≤ ( c + 1 $T(k) \le c \, k$$k < n$ .$T(n) = 2 T(\lfloor n/2\rfloor) + n \le 2 c \lfloor n/2\rfloor + n\le (c+1) \,n$

Это не доказывает индуктивный шаг: вы начали с , и вы доказаличто для к = п , Т ( к ) ≤ ( с + 1 $T(k) \le c \, k$$k=n$ . Это более слабая оценка. Посмотрите, что это значит: T ( k ) ≤ $T(k) \le (c+1) \, k$ означаетчто с является оценка скорости роста Т . Но у вас есть скорость c, которая растет, когда k растет. Это не линейный рост!$T(k) \le c \, k$$c$$T$$c$$k$

Если вы внимательно посмотрите, вы заметите, что скорость увеличивается на 1, когда k удваивается. Итак, неофициально, если m = 2 p k, то c m = c k + p ; другими словами, c k = c 0 log 2 k .$c$$1$$k$$m=2^p k$$c_m = c_k + p$$c_k = c_0 \log_{2} k$

Это может быть сделано точно. Докажите по индукции , что для , Т ( к ) ≤ Ĉ войти 2 ( K ) .$k \ge 1$$T(k) \le c \log_2(k)$

Рекуррентное соотношение типично для алгоритмов «разделяй и властвуй», которые разделяют данные на две равные части за линейное время. Такие алгоритмы работают в время (не O ( n ) ).$\Theta(n\,\mathrm{log}(n))$$O(n)$

Чтобы увидеть ожидаемый результат, вы можете сравнить рекуррентное соотношение с основной теоремой . Деление а дополнительная работа - n ; log 2 ( 2 ) = 1, так что это второй случай, когда рост равен Θ ( $2T(n/2)$$n$$\log_2(2) = 1$ .$\Theta(n\,\log(n))$

Я расширяю уже полученный ответ, возможно, только объясняя свой комментарий более подробно.

$T(n) = a T(n/b) + f(n)$$a \geq 1$$b > 1$$f(n)$$\lfloor n/2 \rfloor$$n/2$, Чтобы быть технически точным, наше повторение может быть не вполне определенным, потому что может не быть целым числом. Однако это разрешено, поскольку это не повлияет на асимптотическое поведение рецидива. Поэтому нам часто бывает удобно бросать полы и потолки. Формальное доказательство этого немного утомительно, но заинтересованный читатель может найти его, например, в Cormen et al. книга .$n/2$

$a = 2$$b = 2$$f(n) = \Theta(n)$$n^{\log_b a} = n^{\log_2 2} = n$$f(n) = \Theta (n)$$T(n) = \Theta (n \log n)$