TIL - 복잡도 분석, 시간 복잡도, 공간 복잡도

시간복잡도 학습목표

1. 내가 짠 코드의 시간복잡도를 스스로 계산이 가능하다
2. 입력 크기를 보고 어떤 복잡도까지 허용되는지 역산할 수 있다
3. 자료구조별 기본 연산의 복잡도 공부하기

 

 

 

문제

- 여러 알고리즘의 시간 복잡도와 공간 복잡도를 이해하고 비교합니다.
- 동일한 문제를 다른 복잡도로 해결하는 방법을 학습합니다.
- 배열에서 중복 원소를 찾는 문제를 여러 방법으로 구현합니다.

 

 

문제풀이

시간복잡도의 효율성에 대한 표이다.

시간복잡도의 개념

 

 

 

1. 이중 반복문

def find_duplicates_brute_force(nums):
    """
    방법1: 이중 반복문 사용
    시간 복잡도: O(n²)
    공간 복잡도: O(k) - k는 중복 원소 개수
    """
    duplicates = []
    n = len(nums)
    
    # 이중 반복문으로 중복 찾기
    for i in range(n-1): 
        for j in range(i+1, n):
        	# 같은 원소를 찾으면 추가
            if nums[i] == nums[j] :
                if not nums[i] in duplicates: # 중복 추가 방지 필요
                    duplicates.append(nums[i])
    
    return duplicates

 

 

이중 반복문으로 중복을 찾고, 같은 원소를 찾으면 추가한다. 이때, 중복 추가 방지가 필요하다.

이중 반복문이기 때문에 n 이 두번 반복돼 시간 복잡도는 O(n²) 이다. (n * n)

공간 복잡도는 O(k) - k는 중복 원소 개수 이다.

 

 

2. 정렬 후 인접 원소 비교

def find_duplicates_sorting(nums):
    """
    방법2: 정렬 후 인접 원소 비교
    시간 복잡도: O(n log n) - 정렬
    공간 복잡도: O(1) - 정렬을 in-place로 수행
    """
    if not nums:
        return []
    
    nums.sort() # sort 하면 값을 반환하는 줄 알았는데 원본 리스트를 수정함.
    
    duplicates = []
    
    # 인접한 원소 비교하여 중복 찾기
    for i in range(0,len(nums)-1): # nums[i+1] 과 비교하니까 범위 설정 중요
        if nums[i] == nums[i+1]:
            if not nums[i] in duplicates:
                duplicates.append(nums[i])
    
    return duplicates

 

list.sort() : sort 하면 원본 리스트를 수정한다. 값을 반환하는 것이 아님

 

외부 range 의 범위가 n - 1 이 되어야 하는 이유를 이해했다. 

n = [1,2,3,4]
마지막 값은 4, i + 1 = 4, i = 3 이 되어야 한다.
n은 4이고, range 는 0부터 시작한다. 
i = 3 의 인덱스는 2이다. 즉, range 의 end는 n - 1 로 입력해야 n -2 까지만 간다.

 

시간복잡도는 O(n log n) 이다. 

 

1. nums.sort()
   1. sort 는 merge sort (병합 정렬) 계열이다. 정렬할 때 반으로 쪼개고 > 정렬하고 > 합친다 과정을 반복한다. 
   2. n 개를 쪼개는 걸 반복 : 반으로 쪼갠다 = 2 로 쪼갠다. = log n
   3. 각 단계에서 하는 일 : 전체 n 개 원소를 한번씩 훑으면서 합치는 작업 
   4. 총 작업량 = (단계 수) * (각 단계에서 하는 일) = log n * n = n log n
2. for i in range(...)
   1. range(0, len(nums) -1) 을 한번 도니까 O(n)
3. if not nums[i] in duplicates
   1. in 이 도는 횟수는 nums 전체 길이 만큼이다. 그럼 그걸 m 이라고 쳤을 때, 최악의 경우는 n 만큼 반복하는거다. 빅오는 최악을 기준으로 놓고 보기 때문에 현재 코드는 n 제곱이다. 

 

즉, 현재 코드는 n 제곱의 시간 복잡도가 나온다. 그럼 이게 log n 이 나오도록 어떻게 할 수 있을까?

 

 

python set 자료형을 활용해서 중복을 제거하고, 최종적으로 반환하였다. 아래 해시 집합에서 set 자료형에 대한 설명을 작성했다. 

Python 의 set 연산자 (집합 자료형)

 

 

def find_duplicates_sorting(nums):
    nums.sort() # sort 하면 값을 반환하는 줄 알았는데 원본 리스트를 수정함.
    
    duplicates = []

    for i in range(0, len(nums) - 1):
        if nums[i] == nums[i+1]:
            duplicates.append(nums[i])
    
    duplicates = list(set(duplicates))
    
    return duplicates

 

 

 

 

3. 해시 집합 사용 

def find_duplicates_hash(nums):
    """
    방법3: 해시 집합 사용
    시간 복잡도: O(n)
    공간 복잡도: O(n)
    """
    seen = set()
    duplicates = set()
    
    for i in nums:
        if i in seen: # list 에 있는지 확인하려면 if "문자열" in list: 를 사용한다.
            duplicates.add(i)
        else:
            seen.add(i)
            
    
    return list(duplicates)

 

if "문자열" in list : list 에 해당 문자열이 포함되어있는지 확인하려면 사용한다.

 

python list 와 set의 연산 원리 차이

해당 원리 차이가 방법 1,2 와 3에서 같은 in을 썼음에도 3에서는 O(n) 을 유지할 수 있게 해주었다. 

Python List & tuple 자료형

파이썬의 리스트나 튜플에서 in 연산자는 값이 존재하는지 확인할 때 처음부터 끝까지 확인해야 하므로 O(n) 시간이 걸린다.

 

Python Set 자료형

python의 set 자료형에서 in 연산자는 값이 존재하는지 확인할 때 평균 O(1) 의 매우 빠른 시간 복잡도를 가진다. 

 

 

 

어려웠던 점

1. 파이썬 문법 중 sort 가 새로운 arr 을 반환하는 줄 알았는데, 원본 리스트를 수정하는 것이었다.
2. 파이썬 문법 2종을 찾아봤다
   1.  if i in list:
   2. nums.sort()
3. 목표는 내가 짠 코드의 시간 복잡도를 역산할 수 있을 정도로 익히는건데, 시간 복잡도를 구하는 기준이 어렵다. 파이썬 자료형들을 정리하면서 익혀야겠다.
4. 시간 복잡도를 쉽게 생각하는 방법이 있을 것 같은데,  좀 더 고민이 필요할 것 같다.
   1. https://cordcat.tistory.com/75#google_vignette