[통계] 알고리즘의 복잡도 (1)

대용량 데이터를 효율적으로 처리하기 위해서는 효율적인 알고리즘이 필수적이다. 같은 기능을 수행하는 알고리즘이라도 시간 효율, 메모리 효율은 다를 수 있다. 이번 게시글에서는 벡터의 내적을 수행하는 두 가지 다른 알고리즘을 예로 들어 시간 복잡도 및 메모리 비용을 측정해보고자 한다. 또한, 알고리즘의 복잡도를 측정하기 위하여 Big-O라는 차수에 대해 다룰 것이다.

1/ 프로그램의 복잡도: 내적

# 내적
01 innerproduct = function(v, w) {
02	sumvalue = 0
03    
04    for (i in 1:length(v)){
05    	sumvalue = sumvalue + v[i] * w[i]
06    }
07    return (sumvalue) 
08}

 

a/ 시간 복잡도

내적 알고리즘에 대한 시간 복잡도

 

b/ 메모리 비용

내적 알고리즘에 대한 메모리 복잡도

 

# 향상된 내적 프로그램: 길이 check 
01innerproductwithcheck = function(v, w){
02    if (length(v) == length(w)){ # 벡터 길이가 같은 경우에만 내적
03     	sumvalue = 0
04        
05        for (i in 1:length(v)){
06        	sumvalue = sumvalue + v[i] * w[i]
07        }
08        return(sumvalue)
09    else{
10    	print("Vector must have the same length!")
11        }
12    }

---

a/ 시간 복잡도

향상된 프로그램에 대한 시간 복잡도

 

b/ 메모리 비용

v, w, i, sumvalue 로 동일하게 유지됨

---

2/ 복잡도의 차수

시간 복잡도와 메모리 비용은 OS 성능, 프로그래밍 스타일 등에 좌우됨

이때, 입력값이 큰 경우에는 추상적 수준의 기저 (알고리즘 효율성)에 대한 성능 비교가 더 중요함

 

a/ Big-O

수학적 order

 

Big-0의 성질

n^k 의 예제

 

b/ 효율성 비교

알고리즘의 비용이 낮을 수록 차수도 낮음

따라서, nlog(n) > n이므로 f1(n)이 더 효율적

 

 

 

---

다음 게시글 - 알고리즘의 여러 차수

2020/12/28 - [분류 전체보기] - [통계] 알고리즘의 복잡도 (2) - 알고리즘의 여러 차수

[통계] 알고리즘의 복잡도 (2) - 알고리즘의 여러 차수

---

 

I'm a Senior Student in Data Science ! 

데이터 사이언스를 공부하고 있는 4학년 학부생의 TIL 블로그입니다. 게시글이 도움 되셨다면 구독과 좋아요 :)