как рассчитать временную сложность для генераторов - PullRequest
Новая
       15

как рассчитать временную сложность для генераторов

0 голосов
/ 08 сентября 2018

Я решил проблему с техникой скользящего окна. Насколько я понял, временная сложность должна быть O (N ^ 2), так как я использовал генераторы / выходы в функции slide_windows, и они не будут выполняться, пока не будут вызваны в цикле. Но платформа, над которой я работаю, рассчитала сложность времени как O (N ^ 3) и оценила мой код как очень эффективный.

Я немного смущен. У меня два вопроса. Первый; Является ли временная сложность следующего кода действительно O (N ^ 3). Во-вторых, Если мое предположение верно и сложность по времени равна O (N ^ 2), все еще очень неэффективно?

Большое спасибо заранее! 

def sliding_windows(iterable, size=3):
    it = iter(iterable)
    windows = []
    for item in range(0, size):
        windows.append(next(it))
    yield windows
    for item in it:
        windows = windows[1:] + [item]
        yield windows

def solution(A):    
    min_average = (A[0] + A[1] + A[2]) / 3
    print(min_average)
    index = 0
    for window_size in range(3, len(A)):
        generator = sliding_windows(A, window_size)
        window_index = 0
        for window in generator:
            average = sum(window) / window_size

            if (average < min_average):
                min_average = average
                index = window_index
            window_index = window_index + 1

    return index
...