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

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

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

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

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

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

~ log N

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


for-loop time-complexity complexity-theory tilde
person Programmer1994    schedule 25.05.2016    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы правы, цикл 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).

person blazs    schedule 26.05.2016
comment
Без проблем. Чтобы было совершенно ясно, вы можете изменить базу на b, но не игнорировать ее --- у вас будет дополнительный множитель log_b 3 с правой стороны (например, S(N) ~ C * ceil(log_b 3 * log_b N)). - person blazs; 26.05.2016