시간복잡도

본격적으로 알고리즘을 공부하려고 한다.

사용 책 : 코딩 테스트 합격자 되기 C++편

강의 주소 : https://www.inflearn.com/course/cpp-EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%95%A9%EA%B2%A9/dashboard

[지금 무료] 코딩 테스트 합격자 되기 - C++ 강의 | dremdeveloper - 인프런

 

 

강의 유튜브 주소 : https://www.youtube.com/watch?v=6oDZgi_7ao0&t=534s

---

알고리즘이란 무엇인가?

• 유한한 수의 규칙에 따라 구별 가능한 기호들을 조작하여 입력 정수에서 출력 정수를 생성하기 위한
  일반화된 작업이다.
• 함수라고도 볼 수 있을 것 같다.($\because$ 입력에 따른 예측가능한 출력)

그렇다면 좋은 알고리즘이란 무엇인가?

• 작동하는 데 걸리는 시간을 측정하여 그 시간이 짧으면 된다.
• 작동하는 실행된 연산횟수를 측정하여 그 시간이 짧으면 된다.

코딩테스트에서는 알고리즘의 성능을 연산횟수로 측정한다.

• 그렇다면 연산횟수를 매번 정확하게 측정할까?
  • 그렇지 않다. '대충 어느정도이다'라고 까지만 알면 된다.
  • 구체적으로 어떻게 대충 말하는 것일까?(대충의 기준은?)
    • 마치, 수학에서 무한대로 극한을 취할 때와 같이 나보다 차수가 낮은 애들은 무시한다.
    • $$
      x! > 2^x(지수함수) > x^n > \cdots > x^3 > x^2 > x > x \log x > \log x(로그함수) > \text{상수}
      $$
    • 따라서, 다항식의 경우 최고차항의 차수가 시간복잡도이다.

자주 보이는 복잡도는 다음과 같다.

이를 어떻게 활용하는가?

• 허용된 시간복잡도를 보고 어떤 알고리즘을 선택할지 결정하는 데 이용된다.
  • 즉, 문제에서 요구하는 성능을 만족하는 알고리즘을 택해야 한다.

메서드의 시간 복잡도를 파악하는 것이 중요하다.

• 동일한 동작처럼 보이지만, 시간복잡도가 다를 수도 있다.
  • 기본 컨테이너 vs Unordered 컨테이너
  • vector와 dictionary/set에서 특정 key 존재 유무 확인하기
  • vect와 list에서 특정 위치 원소 가져오기

실전예시

• 추후 계속 추가