[CS] sort, in, remove의 시간 복잡도

1. sort()

- len(list) 가 N일때 : N log N

 

2. list의 in

- 내부적으로 for문을 돈다 => worst의 경우 O(N)

# 예시
lst = [1, 2, 3, 4, 5]
print(3 in lst)

found = False
for item in lst:
    if item == 3:
        found = True
        break
print(found)

 

*대안 : set이나 dict의 in

- 해시 테이블 기반이라 in 연산이 매우 빠르다 => O(1) 평균

 

3. remove 

- 내부적으로 for문을 돈다 => worst의 경우 O(N)

def remove(x):
    for i in range(len(lst)):    # O(N)
        if lst[i] == x:
            shift elements left  # O(N) in worst case
            return

- shift elements left의 동작 원리

# 예시
lst = [10, 20, 30, 40]
lst.remove(20)

# 동작
Before: [10, 20, 30, 40]
                ↑  ← 삭제 대상

After:  [10, 30, 40]
               ↑  ← 당겨짐!