0.

자료구조와 알고리즘을 공부할 때 핵심은 공간과 시간 이용
공간과 시간은 거의 항상 반비례하는 경향이 있다.

시간 복잡도 : 어떤 알고리즘이 얼마나 걸리는가? ( CPU )
공간 복잡도 : 어떤 알고리즘이 메모리를 얼마나 쓰는가? ( RAM )

1.

1( Constant ) : 입력자료의 수에 관계 없ㄱ이 일정한 실행 시간을 갖는 알고리즘.

$log N$ : 만약 입력 자료의 수에 따라 실행 시간이 이 $log N$의 관계를 만족한다면 $N$이 증가함에 따라 실행시간이 조금씩 늘어난다. 주로 큰 문제를 일정한 크기를 갖는 작은 문제로 쪼갤 때 나타난다. ( 이진 탐색 트리 같은 것 $log_2N$ )

$N$( Linear ) : 입력 자료의 수에 따라 선형적인 실행 시간이 걸리는 경우 입력 자료 가각에 일정량( 시간 )이 할당되는 경우

$NlogN$ : 주로 큰 문제를 일정한 크기를 갖는 문제로 쪼개고( $log N$ ), 다시 하나로 모으는 경우에 나타난다 ( $N$ )

$N^2$( Quadratic ) : 이중루프내에서 입력자료를 처리할 때 발생

$N^3$( Cubic ) : 삼중루프내에서 입력자료를 처리할 떄 발생

$2^n$ : 입력자료가 늘어남에 따라 급격한 실행 시간 증가. 알고리즘을 처음 개발할 때 자주보임

2.

시간 복잡도 : 알고리즘을 구성하는 명령어들이 실행된 횟수 ( Frequency Count ) + 각 명령어의 실행시간 ( Execution Time )을 곱한 합계

그러나 각 명령어의 실행시간은 특정 하드웨어 혹은 프로그래밍 언어에 따라서 값이 달라질 수 있기 때문에 알고리즘의 일반적인 시간 복잡도는 명령어의 실제 실행시간을 제외한 명령어의 실행 횟수만 고려

3.

$\mathcal{O}$ ( 빅 - 오 표기법) — $\mathcal{O}$($N$)
가장 많이 쓰이는 표기법. 알고리즘 실행시간의 상한을 나타내는 경우 ( 최악의 경우 )
$\Omega$( 오메가 표기법 ) — $\Omega$($N$)
오메가 표기법은 알고리즘 실행시간의 하한을 나타내는 표기법 ( 최상의 경우 )
$\Theta$( 세타 표기법 ) — $\Theta$($N$)
세타 표기법은 알고리즘 실행시간의 평균을 나타내는 표기법 ( 평균 )

1
2
3
4
5
6
7
8
9
10
11
12
13
void Func( int *a, int n )
{
    int i = 0;                                      //1
    int j = 0;                                      //1 
    for( i = 0; i < n - 1; ++i )                    //n ( i = 0 일때 부터 i = n - 1일때 까지 계속 실행)
    {
        for( j = i + 1; j < n - 1; ++j )            //( n - 1 ) * n ( 가장 많이 수행 될때 )
        {
            if( a[i] == a[j] )
                a[j] = 0;                           //( n - 1 ) * ( n - 1 )
        }   
    }
}

명령어 실행 횟수를 모두 더하면 $2n^2 - 2n + 2$ -> 상수는 생략하고 최고차항 => $\mathcal{O}$($n^2$)