1. Time Complexity (시간 복잡도)
Time Complexity (시간 복잡도)를 고려한 효율적인 알고리즘 구현 방법에 대한 고민과 Big-O 표기법을 이용해 시간 복잡도를 나타내는 방법
- 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?
2. Big-O 표기법
1. 다양한 시간 복잡도 표기법
- Big-O(빅-오) -> 상한점근
- Big-Ω(빅-오메가) -> 하한점근
- Big-θ(빅-세타) -> 그 둘의 평균
- 위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대해 나타내는 경우이다.
2. 가장 자주 사용되는 표기법
빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문에 빅오표기법을 가장 많이 사용한다.
3. Big-O 표기법의 종류
- O(1)
- O(N)
- O(log N)
- O(N^2)
- O(2N)
1. O(1)
O(1)는 일정한 복잡도(constant complexity)라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.
2. O(N)
O(n)은 선형 복잡도(linear complexity)라고 부르며, 입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.
3. O(log N)
O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며, Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.
4. O(N^2)
O(n2)은 2차 복잡도(quadratic complexity)라고 부르며, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
5. O(2N)
O(2n)은 기하급수적 복잡도(exponential complexity)라고 부르며, Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.
구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해 보는 것이 좋다.
- 피보나치 수열이 O(2N)의 시간 복잡도를 가진 대표적인 알고리즘이다.
* EX)
4. 시간복잡도를 줄이는 방법
1. ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);를 이용!
ios::sync_with_stdio;
장점
c의 stdio와 cpp의 iostream을 동기화 시켜주는 역할을 하는데, 이 때 iostream과 stdio의 버퍼를 모두 사용하기 때문에 딜레이가 발생한다. 그래서ios::sync_with_stdio(false);를 작성해줌으로써 동기화를 비활성화 시켜줍니다. 그 결과 c++의 독립적인 버퍼가 생성되어 실행이 빨라집니다.
- 알고리즘 문제를 풀 때는 대부분 싱글 쓰레드 환경이여서 해당 코드를 추가해도 문제가 발생 하지 않는다
단점
c와의 버퍼가 분리되었기 때문에 C++의 cin과 C의 scanf, gets, getchar 등을 같이 사용하면 안되고 cout과 C의 printf, puts, putchar 등을 같이 사용하면 안된다.
cin.tie(null);
cin.tie(null); 코드는 cin과 cout의 묶음을 풀어줍니다.
기본적으로 cin과 cout은 묶여있고 묶여있는 스트림들은 한 스트림이 다른 스트림에서 각 IO 작업을 진행하기 전에 자동으로 버퍼를 비워줌을 보장합니다.
2. endl구문을 통한 개행X
endl은 개행 문자 출력과 함께 출력 버퍼를 비우는 역할을 해서 딜레이가 발생한다.
그러므로 알고리즘을 풀 때는 실행 속도를 높이기 위해 C스타일의 '\n'을 통해 개행을 한다!
