Я смотрел несколько видео-лекций с сайта opencourseware MIT, и на третьем видео лекции лектор перебирает рекурсивное умножение матриц и сталкивается со сложностью времени:
T(n) = Θ(n<sup>3</sup>)
Для меня очевидно, что мне действительно нужно пересмотреть некоторую мою математику, но я действительно не вижу связи из этого ответа и какого-либо одного из случаев, упомянутых для метода основной теоремы. Я знаю, что рекурсивное отношение имеет вид:
T(n) = a*T(n/b) + f(n) для n> 1.
С этим рекурсивным отношением: a = 8, b = 2 и f(n) = Θ(n<sup>2</sup>).
Итак, как они получили Θ(n<sup>3</sup>)?
Он упомянул это log<sub>2</sub>8 = 3, что имеет смысл. Но я просто не могу понять, какому из трех случаев соответствует рекурсивное отношение в примере, используя значение f(n).
Так как, случай 2 - единственный, где f(n) = Θ(anything), тогда я предполагаю, что это все. Тем не менее, я предполагаю, что моя проблема связана со свойствами логарифмов или показателей.
Если f(n) = Θ(n<sup>log<sub>2</sub>8</sup> * (log<sub>2</sub>n)<sup>k+1</sup>), то как перейти от Θ(n<sup>3</sup>) для f(n) к Θ(n<sup>2</sup>) в случае 2? Чего мне здесь не хватает?