Расчета тильды-сложности для цикла с кубическим индексом

Question

сказать, что я следующий алгоритм:

for(int i = 1; i < N; i *= 3) { 
    sum++ 
} 

мне нужно вычислить сложность с помощью тильды-обозначением, которое в основном означает, что я должен найти тильду-функцию так что, когда я делю сложность алгоритма на эту тильд-функцию, предел в бесконечности должен быть равен 1.

Я не думаю, что есть необходимость в вычислении точной сложности, мы можем игнорировать константы, а затем у нас есть сложность тильд.

Глядя на росте индекса выходного, я полагаю, что этот алгоритм

~ log N 

Но вместо того, чтобы иметь двоичную логарифмическую функцию, база в данном случае 3. ли этот вопрос для точного нотация? Является ли порядок роста точно таким же, и поэтому мы можем игнорировать базу при использовании тильд-нотации? Подхожу ли я к этому правильно?

Answer 1

Вы правы, цикл for выполняет ceil(log_3 N) раз, где log_3 N обозначает логарифм базы-3 N.

Нет, вы не можете игнорировать базу при использовании ноты тильды.

Вот как мы можем определить временную сложность. Будем считать, что каждая итерация цикла for стоит C, для некоторой константы C>0.

Пусть T(N) обозначает количество исполнений цикла for. Поскольку в j-й итерации значение i равно 3^j, то число итераций, которые мы делаем, является наименьшим j, для которого 3^j >= N. Принимая логарифмы базы-3 с обеих сторон, получаем j >= log_3 N. Потому что j является целым числом, j = ceil(log_3 N). Таким образом T(N) ~ ceil(log_3 N).

Пусть S(N) обозначает временную сложность цикла for. Таким образом, «общая» временная сложность составляет C * T(N), так как стоимость каждой из итераций T(N) составляет C, что в тильдовой нотации мы можем написать как S(N) ~ C * ceil*(log_3 N).