알고리즘과 시간복잡도

알고리즘?

알고리즘은 문제를 해결하기 위한 여러가지 해결 방법을 말한다.(찾는 과정)
집으로 가는 지름길도.. 알고리즘이다.

그럼 효율적인 알고리즘이란 무엇일까?

이에 대한 판단 기준이 존재한다.

먼저 공간복잡도라는 개념이 있다.

어떤 입력값이 주어졌을 때, 문제 해결에 메모리 공간이 얼마나 필요한가를 의미한다.
예전에는 꽤나 중요한 개념이었지만.. 시간이 지나면서 컴퓨팅 파워가 너무나 강해졌기 때문에

시간복잡도에 비해 중요도가 떨어지고 있는 것으로 보인다.

⭐️ 시간 복잡도 ⭐️

어떤 입력값이 주어졌을 때, 문제 해결에 시간이 얼마나 걸리는가?

입력값이 늘어났을 때.. 시간은 얼마나 더 걸리는가?
-> 입력값이 늘어나도 시간이 가장 덜 소요되는 알고리즘이 효율적인 알고리즘이다.

알고리즘의 성능(효율성)을 수학적으로 표기하는 방법이 있다.

이를 점근 표기법이라고 하는데, 먼저 빅 오메가 표기법이 있다.

 

빅 오메가(Big-Ω) 표기법은 "최선의 성능이 나올 때 어느 정도의 연산량이 걸리는가?" 이다.
ex. 배열에서 가장 큰 수를 찾는데 첫번째 요소가 가장 큰 수일 경우 필요한 연산량

하지만 알고리즘 분석에서는 보통 '최악의 경우에 대체 시간이 얼마나 걸릴까?'에 더 큰 관심을 둔다.
빅 오(Big-O) 표기법의 개념이 등장한다.

컴퓨터가 연산을 하는것(대입, 비교 등)을 N으로 이를 몇번 하는지 등을 고려해서 계산을 한다.

//배열에서 가장 큰 수를 찾는 알고리즘을 찾는 예시

var someArray = [1, 3, 9, 7, 2]

func getMaxNumInsomeArray(array: [Int]) -> Int {
	var MaxNum = array[0] // 대입 연산 1회
    
    for num in array { //배열의 길이 만큼 아래 연산 실행
    	if num > MaxNum { //비교 연산 1회
        MaxNum = num //대입 연산 1회
        }
    }
    
    return MaxNum
}

 

위 알고리즘을 빅오표기법으로 표시하면.. 
1(대입 연산 1회) + N(배열의 길이만큼) * 2(비교, 대입 연산) => 1 + 2N

즉 2N+1만큼의 시간복잡도를 지닌다.

하지만 상수는 큰 영향을 끼치지 않기 때문에, 위의 경우는 O(N)만큼의 시간복잡도를 가진다고 표기한다.

여기서 보라색 직선의 시간복잡도를 가지는 것이다.
그런데 각 시간복잡도별 곡선을 살펴보면.. x축(n, 입력값)이 증가할 수록,

y축(연산횟수, 소요시간)이 기하급수적으로 늘어나는 경우가 있음을 알 수 있다.

위 그래프에서 가장 효율적인 시간복잡도는 당연 O(1)이다. 입력값이 얼마나 늘어나든 소요시간은 변하지 않기 때문이다.

효율적인 알고리즘을 작성하고, 활용하는데에 있어 시간복잡도라는 개념은 필수적이다.
같은 문제라도 빠르게, 처리량이 많더라도 비교적 리소스를 덜 들여서 문제를 해결할 수 있기 때문이다.
(ex. 이중반복문을 사용하면 O(N^2) 시간복잡도를 지니기에 O(N)으로 해결할 수 있는 방법을 찾는 등)