시간복잡도
일반적으로 c++에서는 1억번의 연산횟수를 1초의 수행시간으로 예측 가능
오메가 표기법 (Ω)
오메가 표기법은 알고리즘의 최선의 경우(best case) 또는 하한 시간복잡도를 나타냄.
세타 표기법 (Θ)
세타 표기법은 알고리즘의 평균적인 경우(average case) 또는 정확한 시간복잡도를 나타냄.
알고리즘의 상한과 하한이 동일할 때 사용됨
빅 오 표기법 (O)
빅 오 표기법은 알고리즘의 최악의 경우(worst case) 또는 상한 시간복잡도를 나타냄.
알고리즘이 실행될 때 필요한 최대 시간 또는 공간을 표현하는 데 사용.
•
알고리즘의 성능을 평가하는 가장 일반적인 방법.
•
입력 크기가 증가함에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 나타냄.
•
상수항과 계수는 무시하고, 가장 빠르게 증가하는 항만을 고려함.
•
가장 많이 중첩된 반복문의 수행 횟수가 시간복잡도의 기준이 된다.
0~100 사이의 숫자에서 원하는 숫자를 찾는 Ω(n)의 시간 복잡도는 1, Θ(n)은 N/2, O(n)은 N이다.
코딩 테스트에서는 여러개의 테스트 케이스들을 사용하므로 빅오 표기법을 기준으로 해야한다.
O(n^2)을 O(nlogn)으로 낮춰야하는 경우가 많다
시간복잡도 활용
Q) N개의 수가 주어졌을 때 이를 오름차순으로 정렬하는 프로그램을 작성해라.
입력: 1≤N≤1000000 의 무작위 숫자 배열
버블정렬 = O(n^2)
병합정렬 = O(nlogn)
연산횟수 = 알고리즘 시간복잡도 n에 데이터의 최대 크기를 대입해서 도출
버블정렬으로는 100만의 수를 2초안에 정렬할 수 없다
따라서 시간복잡도가 낮은 병합정렬을 사용해야함
