프로그래밍/TIL

Do it 알고리즘 코딩 테스트 1장

시간 복잡도 시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말합니다. 일반적으로 수행 시간은 1억번의 연산을 1초의 시간으로 간주하여 예측합니다. 평균 성능을 가진 컴퓨터(CPU)로 사칙연산에 대한 속도를 측정해보면 1초에 약 8.5 X $10^7$(회), 즉 8,500만 회의 연산을 수행합니다 따라서 CPU가 1초에 수행가능한 연산의 횟수를 1억번으로 간주하여 예측하는 것 입니다. 시간 복잡도를 정의하는 방법 빅-오메가( Ω(n) ) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법 빅 - 세타( θ(n) ) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법 빅 - 오 ( O(n) ) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 코딩 테스트에서..