시간복잡도
근 2달동안 java언어의 기초와 더불어 백준 알고리즘문제를 풀어오고있었는데
결국 1년전에 node.js로 어버버 하며 어찌저찌 풀어오던 정렬파트를 다시 만나게되었다.
정렬 알고리즘은 알고리즘을 이해하고 구현함에 있어 반드시 알아야하는 파트이기때문에
이전처럼 답만맞으면 되지 하고 넘어갈게아니고 필수개념이므로
정리 할 필요를 느껴 차근차근 이해해나가보려고 한다.
우선 그 전에 수포자인 나는 정렬알고리즘을 검색하고 찾아볼때마다 함께 따라나오는
시간복잡도를 볼때마다 갑자기 할마음이 식었다.. 그래도 뭐 별수 있겠는가 해야지
그럼 정렬 알고리즘을 하나하나 이해해보기전에 시간복잡도부터 이해하고 넘어가자.
✅ 시간복잡도
🚩시간복잡도 : 알고리즘이 결과를 도출하는데 얼마나의 시간이 걸리는 지에 대한 값으로
좋은 프로그램을 선별하는 기준 중 하나이기도 하다
🚩빅-오(Big-O) : 시간복잡도에는 여러 개념이 있지만 " 아무리 많이 걸려도 이 시간안에는 끝날것 "
즉 처리에 필요한 시간의 최대치를 나타내는 표기법으로 사용된다.
동일한 문제를 해결함에 있어, 같은결과를 가져오더라도 어떤 탐색방법을 사용하냐에 따라 걸리는 시간은천차만별이 될 수도 있고 백준과같은 알고리즘 풀이 사이트에서는 시간제한도있으므로 시간복잡도에 기반한 정렬알고리즘에 대한 이해는 필수적이라고 볼 수 있다.
정렬알고리즘은 종류도 많고 각 정렬별 장단점이 있고 각각의 시간복잡도를 가진다.
시간복잡도의 속도는
O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!) < O(n^n) 로
왼쪽이 가장 빠른 시간복잡도를 가진다.
📌 O(1)
O(1) : 상수시간
- 입력크기와 상관없이 고정된 시간으로 계산한다면 알고리즘이 상수시간(constant time)에 실행된다고한다.
- 입력값 n이 주어졌을 때 , 연산이 한번만 수행된다.
- 인풋의 크기가 소요시간에 영향이 없으며, 반복문이 없으면 대체로 O(1)이다.
- 문제를 해결하는데 오직 한단계 처리
ex) 배열의 n번째 원소에 접근, 스택에 push/pop, 큐에 삽입/삭제,,
public static void main(String[] args){
System.out.println("hello");
}
📌 O(log n)
O(log n) : 로그시간
- 알고리즘의 실행시간이 입력크기의 로그에 비례
- 입력값이 리스트가 아닌 정수를 출력할 때, 정수의 값이 2배로 커지는 경우의 반복문.
- 입력값 n이 128일경우 i가 1일때부터 2,4,8,16,32,64, 가지 총 7번실행하고 log 128 = 7 인 값을 낼 수 있다.
- 문제를 해결하는데 필요한 단계들이 연산마다 특정요인에 의해 줄어듦
ex) 이진탐색 (binary serach) 알고리즘
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int i=1;
while(i<n){
System.out.println(i);
i = i * 2;
}
}
// 2의 거듭제곱을 출력하는 함수이며
// 인풋이 리스트가 아닌 단순 정수이다.
// 문제공간을 매번 절반으로 나눈다.
📌 O(n)
O(n) : 선형시간
- 알고리즘의 실행시간이 입력크기에 정비례한다.
- 문제를 해결하기위한 입력 n만큼의 단계가 필요
ex) 배열에서 검색, 최소/최대값 찾기등의 연산,,
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int i=0;
while(i<n){
System.out.println(i);
i++;
}
}
📌 O(n^2)
O(n^2) : 이차시간
- 알고리즘의 실행시간이 입력크기의 제곱에 비례한다.
- 해당방식의 알고리즘은 각 원소를 다른 모든 원소와 비교한다
- 문제를 해결하기위한 단계의 수는 입력값 n의 제곱
ex) 버블정렬 (bubble sort) , 선택정렬 (selection sort), 삽입정렬(insertion sort)
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int cnt = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cnt++;
}
}
System.out.println(cnt);
}
// 9 를입력했을경우 81이 출력된다.
// 입력값에대한 제곱의 과정이 소요된다.
📌 O(n^3)
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int cnt = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
for(int x=0;x<n;x++){
cnt++;
}
}
}
System.out.println(cnt);
}
// 9 를입력했을경우 9의 3제곱인 729가 출력된다.
📌 O(n log n)
O(n log n) : N 로그 N 시간
- 알고리즘의 실행시간이 입력크기와 입력크기의 로그곱에 비례한다.
- 해당 알고리즘은 입력의 절반(또는 일부) 로 나눌때마다 각 부분을 독립적으로 처리한다
- 문제를 해결하기위한 단계의 수가 n번에 그 하나의 n번당 단계들이 연산마다 특정요인에 의해 줄어듦
ex) 병합정렬(merge sort), 퀵정렬(quick sort) - 평균적인성능, 최악의시간복잡도는 O(n^2), 힙정렬(heap sort)
- 각 깊이별로 분할이 수행되어 합병해야 되는 배열의 수는 많아지지만, 총 원소의 수는 똑같다 (n개)
따라서, 각 깊이별로 수행되는 merge의 시간복잡도는 O(n)이 되며, 이것을 모든 깊이에 대하여(log n개만큼) 수행하기때문에
시간복잡도는 O(n log n)으로 표현할 수 있다.
📌 O(2^n)
O(2^n) : 지수시간
- 피보나치수열을 예로들 수 있으며 재귀가 역기능을 할 경우 해당되고, 데이터량이 많아질수록 처리시간이 기하급수적으로 증가함
- 문제를 해결하기위한 단계의 수는 주어진 상수값2의 n제곱
📌 O(n!)
O(n!) : 계승시간
- 입력데이터의 원소들로 만들 수 있는 모든 순열을 생성
🚩 알고리즘 속 함수 실행시간 도출
- 반복문 : 반복문 내 수문의 실행 시간과 반복 횟수의 곱. 시간 복잡도는 O(n)
- 중첩 반복문 : 모든 반복문 크기의 곱과 반복문 내 구문의 실행 시간을 곱한 것. 반복문 수를 c라고 할 때 시간 복잡도는 O(n^c)
- 연속 구문 : 연속된 구문의 실행 시간을 모두 더한다.
- if-else 구문 : if나 else 중 실행 시간이 더 많이 걸리는 블록을 선택, 나머지는 무시.
- 로그 구문 : 각 반복마다 입력 크기가 일정하게 감소. 시간 복잡도는 O(logn)
🚩 시간 제한이 1초인 문제의 경우
- N의 범위가 500: 시간 복잡도가 O(N³) 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 2,000: 시간 복잡도가 O(N²) 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 100,000: 시간 복잡도가 O(NlogN) 알고리즘을 설계하면 문제를 풀 수 있다.
- N의 범위가 10,000,000: 시간 복잡도가 O(N) 알고리즘을 설계하면 문제를 풀 수 있다.
-출처
https://developercc.tistory.com/1
https://codesyun.tistory.com/104
https://scshim.tistory.com/257
https://zorba91.tistory.com/196