Big-o.md

알고리즘 문제풀이를 하면서 효율성을 테스트할 때 코드의 시간복잡도를 구해 효율적인 알고리즘을 짤 수 있도록 하기 위해서 시간복잡도를 공부해보겠다.

알고리즘

• 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들

• 한가지 상황에 대해 다양한 알고리즘을 사용할 수 있지만 가장 빠른 알고리즘을 구하기 위해 시간복잡도가 가장 낮은 알고리즘을 선택해 사용한다.

즉, 특정 상황에서 가장 빠른 실행속도를 가지는 코드를 짜기 위해 알고리즘을 연구하는 것이다.

알고리즘의 실행시간

• 입력값의 크기

• 입력값의 크기에 따른 함수의 증가량 -> 성장률

이때 중요하지 않은 상수들과 계수를 제거하면 중요한 성장률에 집중할 수 있는데 이것을 점근적표기법-Asymptotic notation 이라고 부른다.

점근적 표기법의 종류

• 최상의 경우 - 오메가 표기법

• 평균의 경우 - 세타 표기법

• 최악의 경우 - 빅오 표기법

평균의 경우를 구하면 정확하고 좋겠지만 평가하기 까다롭다, 그래서 최악의 경우인 빅오를 사용하는데 알고리즘이 최악일 떄의 경우를 판단하면 평균과 가까운 성능으로 예측할 수 있다.

이제부터 빅오 표기법으로 시간복잡도를 구하는 방법을 알아보자

빅오 표기법 - Big-O

빅오 표기법은 불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.

빅오 표기법으로는 시간복잡도와 공간복잡도를 측정할 수 있다.

• 시간 복잡도 - 입력된 N의 크기에 따라 실행되는 조작의 수, 즉 연산하는 횟수

• 공간 복잡도 - 알고리즘이 실행될 때 사용하는 메모리의 양 -> HW의 발전으로 중요도가 떨어짐

• Big-O complexity

시간 복잡도

• 알고리즘을 수행하기 위해 프로세스가 수행해야 하는 연산의 수

왜 실행시간일 아닌 연산수치일까? 실행시간은 HW의 성능, 프로그래밍 언어의 종류 등 상황에 따라 편차가 크게 달라지기 때문에 명령어의 실행 횟수만을 고려하는 것이다.

시간복잡도에서 가장 큰 영향을 미치는 것은 바로 💡 N의 단위이다.

• 자료의 개수가 많은 경우 차수가 가장 큰 항, 즉 최고 차항이 가장 큰 영향을 끼치기 때문에 big-O표기법에서는 가장큰 차수만을 나타낸다.

코드에서 시간복잡도 구하기

• 아래의 코드를 통해 시간복잡도를 구해보자

int sum = 0
for (int i=0; i<=n; i++){
    sum += i
}

• sum = 0 => 1

• int i=0 => 1

• i++ => n

• sum+=i => n -> 1+1+n+n => 2n + 2 식의 최고차항이 2n이기때문에 O(2n+2) => O(n) 이 코드의 시간 복잡도를 big-O표기법으로 표기하면 O(n)이다.

시간복잡도 구하는 tip

• 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)

• 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)

• 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)

• 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)

• 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)

• 컬렉션 정렬을 사용하는 경우 : O(n*log(n))

정렬 알고리즘 시간복잡도