100명의 학생이 교실 안에 있다고 해보자.
펜이 하나 있고, 그 펜을 학생 중 한명에게 줬다.
누구에게 펜을 줬는지 알아보자.
o(n^2)
학생 한명에게 가서 펜이 있는지 물어보고, 다른 99명의 학생이 펜을 갖고 있는지 일일이 물어본다. 이걸 100명에 걸쳐서 한다고 생각하면 된다.
o(n)
각 학생에게 개별적으로 가서 펜이 있는지 물어보는 방식이다.
o(log n)
교실을 두 그룹으로 나누고, "펜이 교실의 왼쪽에 있나요? 오른쪽에 있나요" 라고 물어본 후 어느쪽에 있는지 확인한다. 그리고, 다시 그 그룹을 반으로 나눠서 반복한다. 펜을 가진 학생이 한명만 남았을 때까지 이 과정을 반복한다.
시간 복잡도는 실제 코드의 실행속도와 동일할까?
그렇지 않다.
일반적으로 입력값이 커지면 실행 시간도 길어질 것이라고 예상한다.
하지만, N=10일 때 0.5밀리초가 나오고 N=10000일때 0.2밀리초가 나올 수도 있다.
이런 일이 발생하는 이유는 실제 실행시간은 알고리즘의 효율성 외에도 CPU상태, 메모리 상태, 네트워크 부하, 운영체제의 스케쥴링 등 다양한 요소에서 영향을 받기 때문이다.
그렇다면, 시간 복잡도의 정확한 정의는 뭐야?
Instead of measuring actual time required in executing each statement in the code, Time Complexity considers how many times each statement executes.
시간복잡도는 코드의 각 명령문을 실행하는 데 걸리는 실제 시간을 측정하는 대신, 각 명령문이 몇번 실행되는지를 고려한다.
이 코드를 실행하는데 N초가 걸렸다가 아니라
- 이 반복문은 입력 크기 N만큼 반복된다.
- 이 조건문은 한번만 실행된다.
- 이 중첩 반복문은 n*n만큼 실행된다.
처럼 명령문의 실행횟수를 센다.
public static void main(String[] args)
{
System.out.print("Hello World");
}이 코드는 콘솔 출력을 1번만 한다. 어떠한 OS나 하드웨어를 쓰던간에 관계없이, 코드에서 명령문이 실행되는 횟수는 O(1)이다.
실제 시간은 컴퓨터 성능, 운영체제, 네트워크 상태 등 외부 요인에 영향을 받지만, 명령문 실행 횟수는 이런 외부 요인과 무관하게 알고리즘 자체의 효율성을 객관적으로 평가할 수 있다.
public static void main(String[] args)
{
int i, n = 8;
for (i = 1; i <= n; i++) {
System.out.printf("Hello World !!!\n");
}
}이건 n의 개수에 따라 프린트 명령어의 실행 횟수가 달라진다. 그러므로 O(N)이다.
public static void main(String[] args)
{
int i, n = 8;
for (i = 1; i <= n; i=i*2) {
System.out.println("Hello World !!!");
}
}
이건 log2 N의 시간 복잡도를 갖는다. 초기 값은 1이고, 그 이후로 2배씩 증가한다. 2의 거듭제곱(2⁰, 2¹, 2², 2³, ...)이다.
[참고자료]
