Я читаю Введение в Алгоритмы 3-го издания (Cormen и Rivest) и на стр. 69 в разделе "Решение грубой силы" они что n выбирает 2 = Theta (n ^ 2). Я бы подумал, что это будет в Тета (n!). Почему n выбирает 2, плотно связанный с квадратом n? Спасибо!
Сложность n выбирает 2 в тете (n ^ 2)?
Ответ 1
n выберите 2 is
n(n - 1)/2
Это
n2/2 - n/2
Мы можем видеть, что n (n-1)/2 = & Theta; (n 2), взяв предел их соотношений, когда n переходит в бесконечность:
lim n → ∞ (n2/2 - n/2)/n2 = 1/2
Поскольку это дает конечную ненулевую величину, мы имеем n (n-1)/2 = & Theta; (n 2).
В более общем случае: n выберите k для любой фиксированной константы k is & Theta; (n k), потому что она равна
n!/(k!(n - k)!) = n(n-1)(n-2)...(n-k+1)/k!
Который является полиномом k-й степени по n с ненулевым ведущим коэффициентом.
Надеюсь это поможет!