강의보고 공부한 것을 정리하는 목적으로 작성된 글이므로 틀린점이 있을 수 있음에 양해부탁드립니다. (피드백 환영입니다)

알고리즘의 효율을 측정하려면?

두 알고리즘 A와 B를 비교하려면?

1. A가 B보다 "조금", "많이"빨라요 => 애매모호하다
2. 프로그램을 짜서 실행 속도 비교? => 환경에 의존적이다.
3. 입력이 적은 구간과 많은 구간에서 성능이 확연하게 차이가 날 경우에는 어떡해?

그래서 우리는 대안으로 Big-O 표기법을 사용한다.

BIG-O 표기법 1단계 : 대략적인 계산

• 수행되는 연산(산술, 비교 대입 등)의 개수를 '대략적으로' 판단한다.

O(1)은

int a = 0;
a += 1;

O(N + 1)은

int a = 0;
for(int i = 0; i < N; i++)
	a += 1;

O(N^2 + 1)은

int a = 0;
for(int i = 0; i < N; i++)
	for(int j = 0; j < N; j++)
    	a += i;

이라고 볼 수 있다.

BIG-O 표기법 2단계 : 대장만 남긴다

규칙

1. 영향력이 가장 큰 대표 항목만 남기고 삭제한다.
2. 상수를 무시한다. (ex.2N -> N)

int a = 0;

for(int i = 0; i < N; i++)
	a += 1;

for(int i = 0; i < N; i++)
	for(int j = 0; j < N; j++)
    	a += i;
        
a += 1;

이런 코드가 있다면
O(1 + N + 2 N^2 + 1)
= O(2 N^2)
= O(N^2) 이라고 볼 수 있다.

여기서 O는 Order Of라고 읽는다.

그래서 위 코드는 시간복잡도가 N^2이라고 볼 수 있다.

BIG-O 표기법의 의의

• 입력 N의 크기에 따라 성능이 영향을 받는 정도를 나타낸다.
  

LOG 함수

정리

다양한 상황(재귀함수, 반복문안에서 함수 호출 등)이 많지만 결국 프로그래밍의 속도는 반복문에서 결정된다는 것이기 때문에 반복문을 사용할 때 주의를 해야한다.