알고리즘의 시간 복잡도

COCOBALL·2023년 5월 3일
Big-O 표기법시간복잡도알고리즘
0

알고리즘

목록 보기
22/37
post-thumbnail

알고리즘은 어떤 목적을 달성하거나 결과물을 만들어 내기 위해 거쳐야 하는 일련의 과정들을 의미한다.

알고리즘을 해결할 때 해답을 찾는 과정은 다양하고 여러 가지 상황에 따른 알고리즘은 모두 다르기 때문에 효율적으로 문제를 해결하기 위해서는 시간 복잡도를 고민하여 문제를 해결한다.

알고리즘 시간 복잡도

시간 복잡도(Time Complexity)

시간복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다.

다른 의미로는 알고리즘을 수행하기 위해 프로세스가 수행해야 하는 연산을 수치화한 것이다. 알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’라는 말이다.

→ 시간 복잡도에서 가장 중요하게 보는 것은 가장 큰 영향을 미치는 n의 단위이다.

  • 효율적인 알고리즘을 구현한다는 것은 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 이야기이다.
  • 그리고 이 시간 복잡도는 주로 Big-O 표기법을 사용하여 나타낸다.

🕖 시간 복잡도를 표기하는 방법

  • 최악의 경우 : Big-Ω (빅-오메가) ⇒ 하한 점근
  • 평균의 경우 : Big-θ (빅-세타) ⇒ 평균
  • 최악의 경우: Big-O (빅-오) ⇒ 상한 점근
  • 위 세 가지 표기법은 시간 복잡도를 각각 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.

✋ Big-O 표기법

  • Big-O로 측정되는 복잡성에는 시간과 공간복잡도가 있다.
    • 시간복잡도는 입력된 n의 크기에 따라 실행되는 조작의 수
    • 공간복잡도는 알고리즘이 실행될 때 사용하는 메모리의 양

가장 자주 사용되는 표기법

  • 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.
  • “최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.

👍 시간 복잡도를 "최선"으로 고려한 경우

  • 결과를 반환하는 데 최선의 경우 1초, 평균적으로 1분, 최악의 경우 1시간이 걸리는 알고리즘을 구현했고, 최선의 경우를 고려한다고 가정하자
  • 이 알고리즘을 100번 실행했다면, 최선의 경우 100초가 걸린다.
  • 만약 실제로 걸린 시간이 1시간을 훌쩍 넘겼다면, ‘어디에서 문제가 발생한 거지?’ 란 의문이 생긴다.
  • 최선의 경우만 고려하였으니, 어디에서 문제가 발생했는지 알아내기 위해서는 로직의 많은 부분을 파악해야 하므로 문제를 파악하는 데 많은 시간이 필요하다.

👎 시간 복잡도를 "최악"으로 고려한 경우

  • 최악의 경우가 발생하지 않기를 바라며 시간을 계산하는 것보다는 ‘최악의 경우도 고려하여 대비’하는 것이 바람직하다.
  • 따라서 다른 표기법보다 Big-O 표기법을 많이 사용한다.
  • Big-O 표기법은 ‘입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’ 를 표기하는 방법이다.

⭐️ Big-O 표기법의 종류

  1. O(1)
  2. O(n)
  3. O(log n)
  4. O(n2)
  5. O(2n)
Complexity110100
O(1)111
O(n)110100
O(log n)025
O(n log n)020461
O(n2)110010000
O(2n)110241267650600228229401496703205376

⭐️ O(1)

💡 O(1)는 일정한 복잡도(Constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.

→ 입력값의 크기와 관계없이 문제를 해결하는 데 오직 한 단계만 처리한다.

👉 O(1)의 시간 복잡도를 가진 알고리즘

def O1_algorithm(arr, index){
	return arr[index]
}

arr = [1, 2, 3, 4, 5]
index = 1
result = 01_algorithm(arr, index)
print(result)
  • 위 알고리즘에서는 입력값의 크기가 아무리 커져도 즉시 출력값을 얻어낼 수 있다.
  • 예를 들어 arr의 길이가 100만큼이라도, 즉시 해당 index에 접근해서 값을 반환할 수 있다.

⭐️ O(n)

💡 O(n)는 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

→ 문제를 해결하기 위해서 단계의 수와 입력값이 n이 1:1 관계를 맺는다.

👉 O(n)의 시간 복잡도를 가진 알고리즘

def On_algorithm(n){
	for i in range(n):
		print("do something for 1 second")
}

def another_On_algorithm(n){
	for i in range(2n):
		print("do something for 1 second")
}
  • On_algorithm 함수에서는 입력값이 (n)이 1 증가할때 마다 코드의 실행 시간이 1초씩 증가한다.
  • 즉 입력값이 증가함에 따라 같은 비율로 걸리는 시간이 늘어나고 있다.
  • 그렇다면 another_On_algorithm은 입력값이 1 증가할 때마다 코드의 실행 시간이 2초씩 증가한다.
  • 하지만 이 알고리즘 또한 Big-O 표기법으로는 O(n)으로 표기한다.
  • 입력값이 커지면 커질수록 계수의 의미가 점점 퇴색되기 때문에, 같은 비율로 증가하고 있다면 2배가 아닌 5배, 10배로 증가하더라도 O(n)으로 표기한다.

⭐️ O(log n)

💡 O(log n)는 로그 복잡도(logarithmic complexity)라고 부르며, Big-O 표기법 중 O(1) 다음으로 빠른 시간복잡도를 가진다.

→ 문제를 해결하기 위해서 필요한 단계들이 연산마다 특정 요인에 의해 줄어든다.

👉 O(log n) 의 시간 복잡도를 가진 알고리즘

def binary_search(li, item, first=0, last=None){
	if not last:
		last = len(li)
	midpoint = (last, first) / 2 + first
	if li[midpoint] == item:
		return midpoint
	elif li[midpont] > item:
		return binary_search(li, item, first, midpoint)
	else:
		return binary_search(li, item, midpoint, last)
  • BST(Binary Search Tree)에서는 원하는 값을 탐색할 때, 노드를 이동할 때마다 경우의 수가 절반으로 줄어든다.
    • 예를 들어 up & down 게임으로 예를 들 수 있다.
    1. 1~100 중 하나의 숫자를 30을 골랐다고 가정한다.
    2. 찾고자 하는 수가 50이라면 50보다 작으므로 down을 말한다.
    3. 1~50중의 하나의 숫자이므로 또다시 경우의 수를 절반으로 줄이기 위해 25를 제시한다.
    4. 25보다 크므로 up을 외친다.
    5. 경우의 수를 계속 절반으로 줄여나가면 정답을 찾는다.

→ 매번 숫자를 제시할 때마다 경우의 수가 절반으로 줄어들기 때문에 최악의 경우에도 7번이면 원하는 숫자를 찾아낼 수 있게 된다.

→ BST의 값 탐색 또한 이와 같은 로직으로, O(log n)의 시간 복잡도를 가진 알고리즘(탐색기법)이다.

⭐️ O(n2)

💡 O(n2)는 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

→ 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱이다.

👉 O(n2)의 시간 복잡도를 가진 알고리즘

def O_quadratic_algorithm(n){
	for i in range(n):
		for j in range(n):
			print("do something for 1 second")
}

def another_O_quadratic_algorithm(n){
	for i in range(n):
		for j in range(n):
			for k in range(n):
				print("do something for 1 second")
}

→ 2n, 5n을 모두 O(n)이라고 표현하는 것처럼, n3과 n5도 모두 O(n2)로 표기한다.

→ n이 커지면 커질수록 지수가 주는 영향력이 점점 사라지기 때문에 이렇게 표기한다.

⭐️ O(2n)

💡 O(2n)는 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간복잡도를 가진다.

→ 구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋다.

👉 O(2n)의 시간 복잡도를 가진 알고리즘

def fibonacci(n){
	if(n<=1):
		return 1
	return fibonacci(n-1)+fibonacci(n-2)
}
  • 재귀로 구현하는 피보나치수열은 O(2n)의 시간 복잡도를 가진 대표적인 알고리즘이다.
  • 브라우저 개발자 창에서 n을 40으로 두어도 수초가 걸리는 것을 확인할 수 있으며, n이 100 이상이면 평생 결과를 반환받지 못할 수도 있다.

👍 시간복잡도를 구하는 Tip

  • 하나의 루프를 사용하여 단일 요소 집합을 반복하는 경우 : O(n)
  • 컬렉션의 절반 이상을 반복하는 경우 : O(n/2) → O(n)
  • 두 개의 다른 루프를 사용하여 두 개의 개별 컬렉션을 반복할 경우: O(n+m) → O(n)
  • 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O(n2)
  • 두 개의 중첩 루프를 사용하여 두 개의 다른 컬렉션을 반복할 경우 : O(n*m) → O(n2)
  • 컬렉션 정렬을 사용하는 경우 : O(n*log(n))

정렬 알고리즘 시간 복잡도 비교

자료구조 시간 복잡도 비교

Reference
https://hanamon.kr/알고리즘-time-complexity-시간-복잡도/
https://blog.chulgil.me/algorithm/

profile
COCOBALL
Welcome! This is cocoball world!
이전 포스트

알고리즘에서 데이터 입/출력 받는 방법 with Python

다음 포스트

[자료구조] 큐(Queue) with Python

0개의 댓글