Понимание временной сложности заданного кода

Question

Я кодировал код simple question на основе кода. Он читается следующим образом:

Vasya имеет n пар носков. Утром каждого дня Вася должен надеть пару носков, прежде чем идти в школу. Вечером, когда он приходит домой, Вася снимает использованные носки и отбрасывает их. Каждый м-й день (в дни с номерами м, 2 м, 3 м, ...) мама покупает пару носков Васе. Она делает это поздно вечером, так что Вася не может надеть новую пару носков до следующего дня. Сколько дней подряд проходит до тех пор, пока Вася не выбежит из носков?

Входной

В единственной строке содержит два целых числа п и т (1 ≤ N ≤ 100, 2 ≤ M ≤ 100), разделенных пробелом.

Выход

печати одно целое число - ответ на задачу.

Мое решение заключается в следующем:

int main() 
{ 
    int res,i,n,m; 
    cin >> n >> m; 

    i = 1; 
    res = n; 
    while(res >= i*m) 
    { 
     res++; 
     i++; 
    } 

    cout << res; 
    return 0; 
} 

Какой должна быть временная сложность? Его определенно не O (n), так как мы увеличиваем с шагом m. Будет ли это log n (base m)? Но и оригинал n увеличивается со временем !!!

Просьба указать некоторые обоснования.

Answer 1

Самый важный фактор в RAM computation model будет:

while(res >= i*m) 
{ 
    res++; 
    i++; 
} 

Ограничивающий фактор будет:

n + i < i*m так Рез начинается с п и растет с той же скоростью, как я

i*m-i > n

i > n/(m-1)

Поскольку мы имеем дело с целыми числами здесь, дополнительная оценка будет

i >= 1

Алгоритма будет расти с O(n/m)

Answer 2

это очень хорошее кодирование ... найти сложность времени мы может игнорировать здесь приращение n, когда m преследует с кратным приростом по его собственному значению, например 1m, 2m, 3m, поэтому мы можем игнорировать дополнительные приращения при нескольких приращениях .... так что цикл будет повторяться здесь до тех, m, чтобы переусердствовать значение n (игнорируя приращение n). И завершить Очевидно, что O (n/m). И в течение последовательных дней, когда девушка будет выходить из носка, вы можете распечатать значение (m * i-res) ...