자료구조에 따른 복잡도 차이

Show All

Search

Operation

Example

Big-O

Notes

l[i]

O(1)

l[i] = 0

O(1)

len(l)

O(1)

l.append(5)

O(1)

mostly: ICS-46 covers details

l.pop()

O(1)

same as l.pop(-1), popping at end

l.clear()

O(1)

similar to l = []

l[a:b]

O(b-a)

l[1:5]:O(l)/l[:]:O(len(l)-0)=O(N)

l.extend(…)

O(len(…))

depends only on len of extension

list(…)

O(len(…))

depends on length of … iterable

l1 == l2

O(N)

l[a:b] = …

O(N)

del l[i]

O(N)

depends on i; O(N) in worst case

x in/not in l

O(N)

linearly searches list

l.copy()

O(N)

Same as l[:] which is O(N)

l.remove(…)

O(N)

l.pop(i)

O(N)

O(N-i): l.pop(0):O(N) (see above)

min(l)/max(l)

O(N)

linearly searches list for value

l.reverse()

O(N)

for v in l:

O(N)

Worst: no return/break in loop

l.sort()

O(N Log N)

key/reverse mostly doesn’t change

k*l

O(k N)

5l is O(N): len(l)l is O(N**2)

Show All

Search

Operation

Example

Big-O

Notes

len(s)

O(1)

s.add(5)

O(1)

x in/not in s

O(1)

compare to list/tuple - O(N)

s.remove(..)

O(1)

compare to list/tuple - O(N)

s.discard(..)

O(1)

s.pop()

O(1)

popped value “randomly” selected

s.clear()

O(1)

similar to s = set()

set(…)

O(len(…))

depends on length of … iterable

s != t

O(len(s))

same as len(t); False in O(1) if the lengths are different

s <= t

O(len(s))

issubset

s >= t

O(len(t))

issuperset s <= t == t >= s

s

t

O(len(s)+len(t))

s & t

O(len(s)+len(t))

s - t

O(len(s)+len(t))

s ^ t

O(len(s)+len(t))

for v in s:

O(N)

Worst: no return/break in loop

s.copy()

O(N)

Show All

Search

Operation

Example

Big-O

Notes

d[k]

O(1)

d[k] = v

O(1)

len(d)

O(1)

del d[k]

O(1)

d.get(k)

O(1)

d.pop(k)

O(1)

d.popitem()

O(1)

popped item “randomly” selected

d.clear()

O(1)

similar to s = {} or = dict()

d.keys()

O(1)

same for d.values()

dict(…)

O(len(…))

depends # (key,value) 2-tuples

for k in d:

O(N)

all forms: keys, values, items