Временная сложность операции обрезки по списку - PullRequest
Новая
       6

Временная сложность операции обрезки по списку

0 голосов
/ 21 мая 2019

Что такое сложность времени из операция обрезки в списке (пример ниже)? 

def function():
    list = [1, 2, 3, 4, 5]
    x = list[2:]

    print(x)

Я предполагаю, что это linear O (n) , но не уверен, что это так.

1 Ответ

1 голос
/ 21 мая 2019

сложность нарезки списка 

Slice         | l[a:b]       | O(b-a)        | l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N)

пример со списком операций 

def is_unique1 (alist : [int]) -> bool:
    for i in range(len(alist)):     #O(N) - for every index; see * below
        if alist[i] in alist[i+1:]: #O(N) - index+add+slice+in: O(1)+O(1)+O(N)+O(N) = O(N)
            return False        #O(1) - never executed in worst case; ignore
    return True             #O(1) - always executed in worst case; use

взгляните на это это может помочь вам

...