시간복잡도의 개념과 예제

시간복잡도는 계산시간의 표준이 되는 단위입니다. 계산이 빠른 알고리즘이 훨씬 더 유리하므로 그만큼 시간복잡도의 계산은 중요하게 여겨집니다. 

계산은 컴퓨터 하드웨어 CPU 프로세서를 통해서 이뤄지는데, 당연히 CPU의 성능이 좋으면 계산속도가 빨라집니다.

그 말은 하드웨어에 따라서 계산속도가 달라질 수 있다는 뜻이 되고, 하드웨어 성능과 관계없이 알고리즘 자체 비교를 위한 표준이 필요한데 이를 시간복잡도라고 합니다.

이와 비슷한 개념으로 공간복잡도가 있습니다. 공간복잡도는 메모리 효율이 얼마나 좋은가에 대한 표준으로 보통 시간복잡도와 반비례합니다. 

[시간복잡도 계산방법]

시간복잡도는 계산해야 할 횟수 n에 비례합니다.

#include<iostream>
 
 
using namespace std;
 
int main()
{
    cout << "Hello" <<endl;
    cout << "World" <<endl;
}

위와 같은 코드는 main 함수에서 cout이라는 계산이 총 두번 일어난다.

어떤 입력이 있어도 무조건 두번이 일어나게 되죠. 하지만 위 알고리즘은 시간복잡도가 O(1) 입니다.

그 이유는 시간복잡도란 최악의 경우(계산횟수가 가장 많이 일어날 때)의 시간을 뜻하기 때문에 두번, 세번을 계산하던 상수는 그냥 1로 취급합니다.

하지만 이런 경우는 상황이 달라집니다.

#include<iostream>
 
 
using namespace std;
 
int main()
{
    cin >> n;
 
    for(int i = 0; i<n; i++)
    {
        cout << "Hello" <<endl;
        cout << "World" <<endl;
    }
}

n이 높아지면 높아질수록 계산량이 늘어납니다. 계산속도가 n에 비례하기 때문에 이 코드의 시간복잡도는 O(n)입니다.

최악의 경우(계산을 가장 많이하게 되는 경우)는 n에 의해서 결정되기 때문이죠.

그리고 연산횟수가 가장 높은 항을 시간복잡도로 표시하면 됩니다. 계산횟수가 늘어나면 늘어날수록 가장 높은 차수 이외의 항들은 무시되기 때문입니다.

즉, 처리해야하는 데이터의 수 n에 대한 연산의 합 T(n)을 구한 뒤, 가장 큰 차수를 선택하면 O(n)을 구할 수 있습니다.

[시간복잡도 예제]

Two Earth_)

계속 추가됩니다.