BigO(시간복잡도)

1. 알고리즘이란?

• 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들
• 여러가지 상황에 따른 알고리즘은 모두 다르다. 시간 복잡도가 가장 낮은 알고리즘을 선택하여 사용한다.

알고리즘 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다.

2. 점근적 표기법

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

보통은 최악의 경우를 기준으로 알고리즘 성능을 판단한다.

3. 빅오 표기법

시간 복잡도와 공간 복잡도가 있다.

• 시간복잡도는 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다.
• 공간복잡도는 알고리즘이 실행될 때 사용하는 메모리의 양을 나타낸다.
• 오늘날에는 메모리의 발전으로 공간복잡도의 중요도가 낮아졌다.

지수승이 걸리는 알고리즘은 현실에서 해결하기 어려운 문제라고 한다.

대표적인 예시가 소수 구하기! 이를 이용해서 공개키, 비밀키를 만든다.

참고로, for문에서 i*=2 씩 증가하면서 반복문을 돈다고 해도 절반 이상을 반복하기 때문에

시간 복잡도는 O(n/2), 즉 O(n)이 된다.