전자공학도가 이해하는 알고리즘 평가방법 (Big-O, Omega, Theta)

컴퓨터공학쪽에서는 기본중에 기본 같은 개념이던데,

전자전기공학부 학사 출신인 나는 이번 기회에 처음 들어본 이야기.... (심지어 임베디드 프로그래밍으로 밥벌어 먹고 산지 10년차인데 자기계발이 부족했다는 뜻일까?ㅠ)

암튼,

코드가 효율적으로 잘 짜여져 있는지 보기 위해 평가기준이 필요한데

- 메모리 사용량

- 수행시간

이 일반적인 것 같다.

이를 있어보이게 표현하면

- 메모리 사용량: 공간복잡도

- 수행시간: 시간복잡도

로 일컫는 것 같고 왜 인지 모르겠으나 온라인상에서는 시간복잡도에 관련된 개념들이 훨씬 많던데

내 추측으로는

DDR4 같은 DRAM을 점유하는 비중이 좀 더 커지더라도 빠릿빠릿한 실행속도를 원하는 일반 사용자들이 많기 때문이 아닐까...

필요하면 DRAM은 더 장착하면 되는데 CPU 추가로 장착하는건 불가능하고 통째로 바꿔줘야 하기때문에 비용과 공수에 차이가 크다..?

---

암튼 여기선 시간복잡도를 먼저 살펴보겠다.

아래 그래프가 정말 키포인트다.

앛,

Big-O, Omega, Theta의 개념을 정리하지 않았군

Big-O: 최악의 경우 수행시간

Big-Omega: 최고의 경우 수행시간

Big-Theta: 평균적인 경우 수행시간

 

내 프로그램을 사용하는 일반사용자의 입장에서 생각했을때 내 프로그램에 불만을 갖는 경우는 드럽게 느리게 동작할때 아니겠는가? 프로그램이 쾌적하고 빠릿빠릿하다고 불만 가질 사용자가 있을까 싶다.

그래서 Worst case를 가정하는 Big-O 표기법이 중요한데,

 

그럼 다시 시간복잡도 차트로 돌아와서

 

Running time은 사실상 실제 코드의 수행시간을 의미하기 보다는 입력 데이터 증가에 따라 수행시간이 얼마나 늘어나는지를 평가하기 위한 지표라고 생각하면 되겠다.

저 표를 수박겉햝기로 라도 이해하기 위해 아래 순서를 머리에 박아두고

프로그램짤때 수행시간이 덜 걸리는 방향으로 작성하는게 좋겠다.

[ 수행시간 오래 걸리니 가급적 지향해야 할 알고리즘 순서 ]

n: 입력데이터 수

O(n!), O(상수^n), O(n^상수), O(nlogn), O(n), O(logn)

 

이게 이론만 보니간단한데 실제 코드를 보고 Big-O 계산하라그럼 헷갈릴거 같긴하다...

근데 일단 핵심이론만 장착하면 될거 같은데 내가 이해하는 Key-factor 들은

1. 데이터수 증가에 따른 수행시간 증감을 평가하려는게 Big-O 계산법이다.

2. for, while, do-while같은 반복문이 영향을 크게 준다.

3. 가령 반복문안에 있는 수행함수는 아무리 길어져도 Big-O에 영향을 주지 않는다... 데이터수가 많아지거나 말거나 항상 그 구문은 동일하게 수행될거기 때문이다.

 

Big-O 계산을 실제로 해보지 않고 개념만 대강 이해하고 쓰는 글이라 틀린내용 있어도 난 모름..