#1 시간복잡도(Time Complexity)

 

진정한 지식에 무언가를 얹는 것은 인간의 힘에 더 보태는 것과 같다. - 호러스 맨

 

계산 복잡도 이론(Computational complexity theory)에서 문제를 해결하려는 데에 걸리는 시간과 입력의 함수 관계를 시간 복잡도라고 통칭한다. 당연하게도 퓨어한 수학에 가까운 개념이므로 잘 이해가 가지 않는 것은 당연하다.

 

따라서 우리의 주 관점인 컴퓨터사이언스적인 관점에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열의 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 컴공이나 소프트웨어쪽으로 가면 어차피 죽어라 해야 한다.

 

더 풀어서 설명하자면, 알고리즘에서 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수인 것이다.

 

---

 

실제 시간 복잡도를 정의할 때는 한 가지만 사용하지는 않으며(일반적으로 빅-오(O(n))을 대학 공부할 때 많이 쓰기는 한다) 3가지 유형을 사용한다.

 

시간 복잡도 유형
빅-오메가	최선(best case)
빅-세타	보통(average case)
빅-오	최악(worst)

 

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

int main()
{
    int findNumber;
    srand(time(NULL));
    findNumber = rand() % 100;

    for (int i = 0; i < 100; i++) {
        if (i == findNumber) {
            cout << i;
            break;
        }
    }
}

 

이 간단한 코드는 1과 100 사이의 무작위 값을 찾아 출력하는 코드다.

 

빅 오메가 표기법의 관점에서는 한번에 찾는 것이 최선이므로 O(1).

빅 세타에서는 평균이므로 O(n/2)

빅 오에서는 마지막 시행에서 찾는 것이 최악이므로 O(n).

 

애초에 개념 자체는 그렇게 어렵지는 않고, 이걸 써먹는 것이 문제.

 

이번 C++ 코딩테스트 준비는 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

요 책을 이용한다.