Какова временная сложность этого кода, где он может пойти бесконечный цикл?

Question

Я пытаюсь найти временную сложность этого кода.

 while(m!=4){
        if(m>n)
               m=m-n
        else
               n=n-m
    }

Я пробовал случайные значения для m & n, что делает его бесконечным циклом.Я не знаю, как его найти?

Answer 1

Ваш код попадет в бесконечный цикл почти для всех m и n, так как для большинства m и n один из них достигнет 0, и он станет бесконечным циклом (n = n - 0).Кроме того, m должно быть больше 4, иначе цикл будет продолжаться до тех пор, пока m или n не достигнет 0, опять же, тот же случай.Единственный способ завершить ваш цикл - это когда m - n k = 4, где k является целым числом.Или, когда m больше n, m - (nm k) = 4. В этом случае временная сложность будет O (| mn |), линейной в худшем случае.

Answer 2

Эта временная сложность имеет смысл, только если алгоритм завершается.Необходимое условие gcd(m, n) | 4.Но этого недостаточно.

Теперь легко увидеть, что наихудший случай (самое медленное уменьшение) происходит при m = 1 или n = 1, так что сложность равна O(max(m, n)).