Понимание временной сложности в двух вложенных циклах while

Я наткнулся на этот код. Он сканирует элементы массива только один раз. Но меня смущает наличие двух вложенных циклов while, увеличивающих сложность до O (n ^ 2). Код выглядит следующим образом:

def summaryRanges(nums):
    x, size = 0, len(nums)
    ans = []
    while x < size:
        c, r = x, str(nums[x])
        while x + 1 < size and nums[x + 1] - nums[x] == 1:
            x += 1
        if x > c:
            r += "->" + str(nums[x])
        ans.append(r)
        x += 1
    return ans

Я изучаю алгоритмы, поэтому, пожалуйста, поправьте меня, если я где-то ошибаюсь. Спасибо!!


data-structures time-complexity
person deep    schedule 23.07.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Ваш вопрос не ясен на 100%, но если вы имели в виду, почему это НЕ O (N ^ 2) при наличии циклов вложения, то:

Хотя существуют вложенные циклы, они работают с одним и тем же пространством, используя одну и ту же переменную для продвижения итерации. поскольку внутренний цикл не возвращается назад, и всякий раз, когда он движется вперед, он также толкает внешний цикл вперед (на точно такое же расстояние), итерация не будет увеличиваться больше, чем M, если N увеличивается на M (если N1 = N0 + M ). O(N^2) означает, что по мере роста N число итераций растет экспоненциально.

person Amit    schedule 23.07.2015