Я читав час розрахунку складності, пов'язані з питанням на SO, але я не можу коментар там (недостатньо повторень). Яка складність цього алгоритму розбиття на Паліндроми?
У мене є питання щодо переходу від 1-го до 2-го рівняння:
Тепер ви можете написати той же вираз для H (n-1), а потім замінити назад спростити:
H (n) = 2 H (n-1) + O (n) =========>
І це вирішує
H (n) = O (n * 2 ^ n) =========> Рівн
Може хтось проілюструвати, як він отримав рівняння від Eq.1? Дякую.
Відповіді:
2 для відповіді № 1Формула 1 являє собою a рекуррентне відношення. Див. Посилання для підручника про те, як вирішити ці типи рівнянь, але ми можемо вирішити за допомогою розширення, як показано нижче:
H(n) = 2H(n-1) + O(n)
H(n) = 2*2H(n-2) + 2O(n-1) + O(n)
H(n) = 2*2*2H(n-3) + 2*2O(n-2) + 2O(n-1) + O(n)
...
H(n) = 2^n*H(1) + 2^(n-1)*O(1) + ... + 2O(n-1) + O(n)
since H(1) = O(n) (see the original question)
H(n) = 2^n*O(n) + 2^(n-1)*O(1) + ... + 2O(n-1) + O(n)
H(n) = O(n * 2^n)
1 для відповіді № 2
Нам необхідно гомогенізувати рівняння, в цьому простому випадку, просто додаючи постійну до кожної сторони. По-перше, позначте O (n) = K, щоб уникнути зливання з позначенням O на цьому етапі:
H (n) = 2 H (n-1) + K
Потім додайте K для кожної сторони:
H (n) + K = 2 (H (n-1) + K)
Нехай G (n) = H (n) + K, то
G (n) = 2 G (n-1)
Це добре відомий однорідний 1-й порядок повторення, з розчином
G (n) = G (0) × 2н = G (1) × 2н-1
Оскільки H (1) = O (n), G (1) = H (1) + K = O (n) + O (n) = O (n),
G (n) = O (n) × 2н-1 = O (n × 2н-1) = O (n × 2н)
і
H (n) = G (n) - K = O (n × 2н) - O (n) = O (n × 2н)
1 для відповіді № 3
Вони помиляються.
Припустимо, що O позначає щільну зв'язок і замінник O(n) з c * n для деякої постійної c. Розгортаючи рекурсію, ви отримаєте:
Коли ви закінчите, розкрутіть рекурсію n = i і b = T(0).
Тепер знаходимо суму:
Підсумовуючи ви отримаєте:
Тому тепер зрозуміло, що T(n) є O(2^n) без будь-якого n
Для людей, які все ще скептично ставляться до математики:
- рішення F (n) = 2F (n-1) + n
- рішення F (n) = 2F (n-1) + 99n