[자료구조/알고리즘] 1. Intro (시간복잡도)

1. 좋은 알고리즘이란?

알고리즘이란?

• 문제를 해결하는 방법이다.

좋은 알고리즘이란?

• 문제를 효율적으로 (속도 빠르고, 메모리는 적게) 해결하는 방법이다.

프로그램 = 자료구조 + 알고리즘

2. 복잡도(Complexity)

자료구조의 효율성은 자료구조에 대해 수행되는 연산의 수행시간으로 측정한다.

수행시간을 나타내는 시간복잡도(Time Complexity)와 사용되는 메모리 공간의 크기를 나타내는 공간복잡도(Space Complexity)에 기반하여 측정

대부분의 경우, 시간복잡도만을 사용하여 성능을 분석한다.

3. 점근표기법(Asymptotic Notation)

수행시간은 알고리즘이 수행하는 기본 연산 횟수를 입력 크기에 대한 함수로 표현한다.

F(N)

이러한 함수는 다항식으로 표현되며, 이를 입력의 크기에 대한 함수로 표현하기 위해 점근표기법을 사용한다.

3-1. 점근표기법의 종류

1. O(Big-O)표기법
2. Ω(Big-Omega)-표기법
3. Θ(Theta)-표기법 등

4. Big-O 표기법

result = 0
for i in range(n):
	result += i
print(result)

위 코드는 1부터 n까지 더하는 코드로, 연산을 n번 수행
이 코드의 시간복잡도는 O(n)

result = 0
for i in range(n):
	for j in range(n):
		result += j
print(result)

result = 0
result2 = 0
for i in range(n):
	for j in range(n):
		result += j
for i in range(n):
	result2 += i
print(result + result2)

위 두 코드의 시간복잡도는 모두 O(N^2)

4-1. 자주 사용되는 Big-O

• O(1) : 상수시간(Constant Time)

  • 입력값이 아무리 커도 실행시간 일정
  • 최고의 알고리즘

• O(logN) : 로그 시간 (Logarithmic Time)

  • 실행시간은 입력값에 영향을 받지만, 큰 n에 대해서도 매우 빠르다.
  • 이진검색 알고리즘의 수행시간

• O(N) : 선형시간(Linear Time)

  • 입력값에 비례해서 수행시간이 증가한다.

• O(NlogN) : 로그선형시간(Log-linear Time)

  • 대부분의 효율 좋은 정렬 알고리즘의 수행시간
  • 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(nlogn)보다 빠를 수 없다.

• O(N^2) : 제곱시간(Quadratic Time)

  • 버블정렬같은 비효율적인 알고리즘의 수행시간