Итак, мои рекуррентные отношения следующие:
T(n) = O(1) if n < 100
T(n) = 2T(n/3) + n otherwise
Я использовал метод итерации, и в результате получилось, что big-O:
O(n^(log in base 3 of n))
Мне это кажется немного странным (особенно для упражнений, к которым я привык), но верно ли это?
Если вам нужны мои шаги, я добавлю их (не знаю, как отформатировать текст для суммирования и прочее, но если это необходимо, я постараюсь)
Edit:
Применяя метод итерации, я обнаружил, что T (n) на шаге 'i' равен
T(n) = (2^i)T(n/(3^i)) + n * (sum from k = 0 to i of (2/3)^k)
Так как i = log base 3 из n
T(n) = 2^(log base 3 of n) + n * (sum from k = 0 to log base 3 of n of(2/3)^k)
Сумма составляет O ((2/3) ^ log base 3 of n). Если я умножу это на n, я получу
O(n^(log base 3 of n))
Это мой старый результат. Благодаря 'yuvgin' я заметил, что сначала я могу изменить базу:
(2/3)^log base 3 of n = n ^ log base 3 of (2/3)
И тогда я могу упростить базу журналов 3 из (2/3)
n ^ log base 3 of (2/3) = n ^ ((log base 3 of 2) - (log base 3 of 3))
Логарифмическая база x из x равна 1, поэтому:
O(n^log base 3 of 2)
Edit2:
Итак, я нашел эту ссылку: https://math.stackexchange.com/questions/1742712/how-to-solve-the-recurrence-tn-2tn-3n
Это объясняет, как мое суммирование равно O (n), но разве мой результат тоже не должен быть верным, поскольку предполагается, что сумма меньше или равна той же сумме, но бесконечной?