시간 복잡도와 빅오 표기법

두 번째 글이에요...힘든데 너무 재밌네요
시간복잡도 진짜 너무 모르겠어 너무 좋다
이 글은 동아리 발표를 위한 글입니다.
저는 수학 동아리이기 때문에 수학에 관련된 내용으로 골라 보았습니다.

🫧 그래프란?

그래프란 노드와 노드간을 연결하는 간선으로 구성된 자료 구조입니다.
부모/자식 노드의 관계처럼 상하관계가 존재하지 않으며, 방향성이 있는 그래프와 없는 그래프가 있습니다.

🫧 트리란?

트리는 특정한 조건이 있는 그래프입니다. 개체들 간의 계층을 표현한 그래프이기 때문입니다. 반드시 한 개의 경로(단방향)을 가지고, top to bottom 형식이 일반적입니다.

🫧 그래프 트리 탐색 알고리즘의 종류

💬 DFS(Depth-First Search)

한 노드에서 해당 분기를 완벽히 탐색한 후 타 노드로 넘어가는 순회 방법입니다.

💬 BFS(Depth-First Search)

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.

시간 복잡도

우리는 예를 들어 수학 문제를 풀 때 '더욱 효율적인 방법은 없을까'를 고민합니다. 컴퓨터의 작동에서도 이것은 예외가 아닙니다. 실행시간을 줄이기 위해 먼저 이를 예측하는 단계가 필요한데, 이를 표기법 세 가지로 다룰 수 있습니다.

최상의 경우 : 오메가 표기법 (Big-Ω Notation)
평균의 경우 : 세타 표기법 (Big-θ Notation)
최악의 경우 : 빅오 표기법 (Big-O Notation)

프로그램을 짤 때 이 중 최악의 경우를 가정해 고려하기 때문에, 빅오 표기법에 대해 알아보겠습니다.

💬 빅오 표기법

1. O(1)
   일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않습니다.

2. O(n)
   f(n) = n 과 같은 형태로, 입력값이 1 늘어남에 따라 코드의 실행 시간이 1초씩 늘어납니다.

3. O(log n)
   f(n) = log n과 같은 형태입니다. 노드를 이동할 때마다 경우의 수가 반으로 줄어드는 경우 등이 해당합니다.(UP&DOWN 게임이라고 할 수 있습니다.)

4. O(n2)
   f(n) = n^2의 형태입니다. 2차 복잡도라고 부르며 입력값이 증가함에 따라 시간이 n^2의 비율로 증가합니다.

5. O(2n)
   f(n) = 2^n의 형태입니다. 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가집니다.

💬 실제 적용 예시

void  Func(int *a, n)

{
int i=0, j=0;
for (i = 0 ; i < n-1 ; i++){
	for(j=i+1; j<n ; j++) {
    	if (a[i] == a[j]) a[j] = 0 ; 
    	}
    }
}

위의 예시를 바탕으로 적용하면 2n²-2n+2이 나오고,
O(n²)로 표현할 수 있습니다.