반응형
코딩테스트/알고리즘
-
[알고리즘 코딩테스트] 시간 복잡도 표기법 알아보기코딩테스트/알고리즘 2023. 1. 25. 21:01
📑 시간 복잡도 정의하기 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟를 말한다. 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다. 실제 시간 복잡도를 정의하는 유형은 다음과 같다. 📌 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 📌 빅-세타(θ(n)) : qhxhddlf EO(average case)의 연산 횧수를 나타내는 표기법 📌 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 우리는 알고리즘을 풀때 항상 최악일 떄, 즉 데이터의 크기가 가장 클 때를 기준으로 하기 때문에 빅-오 복잡도를 사용해야 한다. 빅오 복잡도는 다음과 같다. 📑 시간 복잡도를 바탕으로 코드 개선하기 시간 복잡도는 작성한 ..