기본기 톺아보기 #1 - 시간복잡도

이동욱·2022년 1월 6일
0

기본기 톺아보기

목록 보기
1/5

시간복잡도란?

  • 알고리즘의 실행 속도

주요요소

  • 반복문이 지배한다.
    • if 문 몇개 추가하고 그런게 중요한게 아니라 반복문 선언이 중요함

표기법

Big O (빅-오) 표기법: O(N)

  • 알고리즘 최악의 실행 시간을 표기
  • 가장 많이/일반적 으로 사용함
  • 아무리 최악이라도 보장하는 최소 성능
  • 표현식에 가장 큰 영향을 미치는 n의 단위로 표기

입력 n에 따라 결정되는 시간 복잡도 함수

  • O(1) < O(logn) < O(n) < O(nlogn) < O(n2n^2) < O(2n2^n) < O(n!) 순서 정도가 많이씀

표현식 계산 방법

O(1)

  • n값에 관계없이 상수회 실행
def print_item(something_list, item_num):
	print(something_list[item_num])
  • 리스트의 길이와 상관없이 요소 하나만 찾아 반환하므로 시간복잡도는 O(1)
  • 반복문이 없으면 대체로 시간 복잡도가 O(1)

O(n)

n에 따라 n번, 2n번, 4n+2 번 등등 실행 → 모두 O(n) 으로 표기

def print_double_forloop(n):
	for i in range(n):
		print(i)

	for j in range(n):
		print(j)

O(n2n^2)

n에 따라 n2n^2번, n2+100n^2 +100 번 등등 실행 → 모두 O(n2n^2) 으로 표기

def print_double_forloop(n):
	for i in range(n):
		for j in range(n):
			print(i * j)

O(lognlogn)

n의 탐색범위가 진행될때마다 절반씩 줄어든다 → O(lognlogn) [트리 사용시 관찰]

def binsearch(x_list, target):
  min_point, max_point = 0, len(x_list)

  while True:
    if a == b:
      return -1

    center = (a + b) // 2

    if x_list[center] == target:
      return center
    if x_list[c] > target:     # 구간을 왼쪽 절반으로 줄임
      min_point, max_point = min_point, center
    else:             # 구간을 오른쪽 절반으로 줄임
      min_point, max_point = center + 1, max_point
def print_powers_of_two(n):
    i = 1
    while i < n:
        print(i)
        i = i * 2

O(2n)2^n)

O(lognlogn) 과 반대로 n이 늘어날 때마다 약 두배씩 늘어난다. → O(2n)2^n)

function func (num){
  if(num <= 1){
    return num;
  }else{
    return func(num-1) + func(num-2);
  }
}
profile
공부해서 남주자

0개의 댓글