[알고리즘] 시간복잡도와 공간복잡도

ljkgb·2021년 2월 27일
0

알고리즘

목록 보기
3/4

시간과 공간

  • 우리는 알고리즘을 통해 원하는 결과가 빨리 나오길 바라지만 컴퓨터의 저장공간(메모리)의 제약이 발생한다. 이에 좋은 알고리즘을 평가하기 위해서는 시공간을 기준으로 평가하게 된다.

시간 복잡도(Time Complexity)

  • 컴퓨터 사양이나 사용한 프로그래밍 언어등 다양한 외부 환경으로 인해 프로그램이 들오가는 시간으로 알고리즘을 평가하기엔 어려움.
  • 그래서 데이터가 많아질수록 걸리는 시간이 얼마나 급격히 증가하는지를 나타내는 '시간복잡도'를 이용

점근표기법(Big-O)

  • 알고리즘의 효율성을 표현하는 방법
  • n이 크다고 가정(n이 크지 않으면 안좋은 알고리즘이라도 문제없음=큰 차이가 없음)
  • 절대적인 시간이 아닌 성장성을 봄

1. 인풋리스트의 길이와 알고리즘 소요시간을 비교

  • O(1)알고리즘: 인풋사이즈에 영향을 받지 않음

  • O(n)알고리즘: 인풋사이즈가 2배 → 걸리는 시간이 약 2배가 됨(인풋사이즈가 10배면 시간도 약 10배)

  • O(n²)알고리즘: 인풋사이즈 2배 → 걸리는시간 4배(2²)

    nO(1)O(n)O(n²)O(n³)
    1001초1초1초1초
    2001초2초4초8초
    10001초10초100초1000초
    100001초100초100001000000초

    * n = 예) 인풋 리스트의 길이

    여기서 O(1)은 인풋 크기와 상관없이 실행되는 코드! 그렇지 않은 코드는 시간 복잡도를 따져봐야 한다.

    알고리즘 소요시간의 격차가 Big-O의 제곱 값이 커질수록 급격히 커지기 때문에 컴퓨터 사양이나 프로그래밍 언어가 아무리 좋다고 하더라도 알고리즘이 별로라면 한계가 생김 = 알고리즘은 중요하다!!

2. 선형탐색 알고리즘 평가

def linear_search(element, some_list):             
	i = 0                                  #O(1)
  n = len(some_list)                           #O(1)
                                                    
  while i < n:                                 #O(1)X반복횟수
  	if some_list[i] == element:                 
  		return i                            
    	i += 1                                      
return -1                                      #O(1)

1) while문을 한번 반복하여 값을 찾은 경우
O(1) + O(1) + O(1) + O(1) = O(4) = O(1)
* O(4)은 O(1)와 동일

2) 리스트에 찾는 값이 없는 경우
O(1) + O(1) + O(n) + O(1) = O(n+3) = O(1)

2. 이진탐색 알고리즘 평가

def binary_search(element, some_list):                      
  start_index = 0                                    #O(1)
  end_index = len(some_list) - 1                     #O(1)
  
  while start_index <= end_index:                    #O(1)X반복횟수
      midpoint = (start_index + end_index) // 2           
      if some_list[midpoint] == element:                  
          return midpoint                                 
      elif some_list[midpoint] > element:                 
          end_index = midpoint - 1                        
      else:                                               
          start_index = midpoint + 1                      
  return None                                        #O(1)

1) while문을 한번 반복하여 값을 찾은 경우
O(1) + O(1) + O(1) + O(1) = O(4) = O(1)
* O(4)은 O(1)와 동일

2) 리스트에 찾는 값이 없는 경우
O(1) + O(1) + O(log n) + O(1) = O(log n) + 3 = O(log n)
* 이진탐색은 찾는 값의 범위가 절반씩 줄어드니 log사용

공간 복잡도(Space Complexity)

  • 인풋 크기에 비례해서 알고리즘이 사용하는 메모리 공간

공간 복잡도도 점근표기법으로 표현 가능( = Big-O 표기법 사용가능)

파이썬에서의 시간복잡도

  • type : O(1)
  • max, min : O(n)
  • str : O(logn) or O(d) (파라미터가 n이고 n의 자릿수가 d일 때)
  • append : O(1)
  • insert : O(n)
  • del : O(n)
  • index : O(n)
  • reverse : O(n)
  • sort, sorted : O(n lg n)
  • slicing(슬라이싱) : O(b−a) (list[a:b] 일 때)
  • len : O(1)
profile
🐹

0개의 댓글