Я очень новичок в алгоритмах и временной сложности и просматриваю книгу. Из того, что я знаю о функции Big-Oh, она не уникальна для любого f(n), в зависимости от констант c и n0. Мое первое сомнение заключается в том, дает ли Основная теорема наилучший случай функции Большого О или нет. Мое второе сомнение - может быть глупое - я запутался после решения задач 1 и 2, пытаясь вернуться назад и проверить ответы.
Теперь моя попытка выглядит следующим образом:
1)cn2≥3T(n/2) + n2
⇒kn2 ≥T(n/2)
⇒k''(n/2)2≥T(n/2) < br> так что это согласуется с O(n2).
Почему то же самое не относится к задаче 2, то есть почему это не O( n2), но O(n2logn)? Я предполагаю, что за этим стоит какая-то математика, и я хочу это знать (если у меня есть достаточный опыт до сих пор).
