Какова сложность этого цикла while?

Question

Пусть m - размер массива A, а n - размер массива B. Какова сложность следующего цикла while?

while (i<n && j<m){ if (some condition) i++ else j++}

• Пример для массива: A = [1,2,3,4] B = [1,2,3,4] цикл while выполняется максимум 5 + 4 раза O(m + n).
• Пример для массива: A = [1,2,3,4,7,8,9,10] B = [1,2,3,4] цикла whileвыполняется не более 4 раз O (n).

Я не могу понять, как представить сложность цикла while.

Answer 1

Один из распространенных подходов - описать сложность времени наихудший случай .В вашем примере наихудшая временная сложность равна O ( m + n ), потому что независимо от того, что some condition во время данной итерации цикла,общее количество итераций цикла не более m + n .

Если важно подчеркнуть, что временная сложность имеет меньшую верхнюю границу в некоторых случаях, тогдавам нужно выяснить, что это за дела, и найти способ их выразить.(Например, если данный алгоритм принимает массив размером n и имеет наихудший случай O ( n ² ),можно также описать его как « O ( mn ) время, где m - это число различных значений вмассив "- только если это правда, конечно, - где мы ввели дополнительную переменную m , чтобы позволить нам отразить влияние на производительность наличия большего или меньшего количества повторяющихся значений.)