[파이썬 자료구조] 03. 알고리즘의 성능

1. 알고리즘 수행 시간

 1) 알고리즘의 효율성

 자원을 얼마나 효율적으로 사용하는가로 판단, 여기서 자원은 시간, 저장 공간, 네트워크 대역 등이 될 수 있음.

=> 대부분 수행 시간과 관련되어 있다!

 2) 알고리즘 수행 시간

 입력의 크기에 대해 시간이 얼마나 걸리는지로 표현

 ex) 정렬: 정렬하고자 하는 원소의 수(=입력의 크기)

       도시 간 최단 거리: 도시의 총 수와 도시 간 도로의 총 수(=입력의 크기)

       팩토리얼: 팩토리얼을 구하고자 하는 자연수의 크기(=입력의 크기)

 

 상수 시간에 비례

sample1(A[], n):
	k <- [n/2]
	return A[k]

 

n에 비례

sample(A[], n):
	sum<-0
    for i <-0 to n-1
    	sum <- sum+A[i]
    return sum

factorial(n):
	if (n=1) return 1
    return n*factorial(n-1)

n^2에 비례

sample3(A[], n):
	sum <- 0
    for i <- 0 to n-1
    	for j <-0 to n-1
        	sum <- sum + A[i]*A[j]
    return sum

sample5(A[], n):
	sum <- 0
    for i <- 0 to n-2
    	for j <- i+1 to n-1
        	sum <- sum + A[i]*A[j]
    return sum

 

n^3에 비례

sample4(A[], n):
	sum <- 0
    for i <-0 to n-1
    	for j <- 0 to n-1
        	k <- A[0...n-1]에서 임의로 [n/2]개를 뽑은 것들 중 최댓값
            sum <- sum+k
    return sum

 

=> 수행 시간을 지배하는 부분이 어디인지 파악하는 것이 우선!!

 

2. 알고리즘 복잡도

1) 점근적 복잡도(Asymptotic Complexity): 입력의 크기가 충분히 클 때의 복잡도, 최고차항의 차수만 중요하고 나머지는 다 무시한다. 

2) O-표기

 어떤 알고리즘에서 입력의 크기가 n이라고 가정했을 때 충분히 큰 입력에 대해 어떤 경우든 n^2에 비례하는 시간을 초과하지 않으면 O(n^2)의 수행시간을 가졌다고 말한다. 

 -n^2 뿐만 아니라 nlogn 등도 포함되지만 후자의 경우 정보 손실이 생긴다. 

3) Ω-표기

Ω^2은 O(n^2)과 정반대. 최고차항의 차수가 n^2보다 작지 않은 모든 함수의 집합

4) Θ-표기

Θ(n^2)은 최고차항의 차수가 정확히 n^2인 모든 함수의 집합

 - Θ(n^2)은 O(n^2)과 Ω(n^2)의 교집합이다. 

 

3. Big-O의 수학적 정의

 

📒쉽게 배우는 자료구조 with 파이썬 연습문제 풀이

01. 

1) True

2) False

3) True

4) True

5) True

6) True

7) True

8) True

9) True

10) False

 

02. 

O(n)

 

03. 

O(n^2), Ω(n^2), Θ(n^2)

 

04. 

Θ(n^3)

 

05. 

O(n^2), Ω(n)

 

06. 

O(n^2), Ω(n)

 

07.

Θ(n^2)