시간 복잡도 (Time Complexity) 심화

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ]

흔히 실수하는 예시

• for - while 중첩 되었다고 O(n^2)이 아니다.

def longestConsecutive(nums):
    nums = set(nums) # O(n) 중복된 숫자를 없애기 위함
    answer = 0
    
    for num in nums: # O(n)
        if num -1 not in nums:
            cnt = 1
            while num + 1 in nums:
                num += 1
                cnt += 1
            answer = max(answer, cnt)
    return answer

nums = [1,2,3,1,8,4,5,6,7,8,9,10]
print(longestConsecutive(nums)) # 10

상수 시간도 완전 무시할 순 없다.

해시테이블 생성은 리스트 생성처럼 O(n)

동작 방식을 알아야 한다

• O(V+E)

def bfs(graph, start_v):
    visited = [start_v]
    queue = deque(start_v)
    while queue:
        cur_v = queue.popleft()
        for v in graph[cur_v]:
            if v not in visited:
                visited.append(v)
                queue.append(v)

    return visited

재귀의 시간복잡도

• 계산이 가능은 하지만, 엄밀하진 못하다.
• overhead가 크다.
• 따라서 보수적으로 계산해야한다.

백트래킹의 시간복잡도

• 계산이 불가한 영역이 있다
• nqueen

코테 실전 적용

기준점: 10^8
시간복잡도는 만능이 아니다. (70%는 계산하면 도움이 된다.)
풀이에 대한 확신
알고리즘 떠올리기