목록2025/04/26 (1)

변수의 기록

시간 복잡도와 점근적 표기법: 알고리즘의 실행 시간 분석하기

1. 시간 복잡도란?**시간 복잡도(Time Complexity)**는 어떤 함수나 알고리즘이 **입력값의 크기(n)**에 따라 얼마나 많은 연산을 수행하는지를 표현한 것. 다시 말해, 알고리즘이 실행되기까지 필요한 연산 스텝의 수를 의미한다.이때 중요한 건, 정확한 시간(초)이 아니라 입력의 크기 n에 따라 시간이 어떻게 증가하는지를 분석하는 것.2. 점근적 분석이란?시간 복잡도를 분석할 때는 보통 입력값 n이 **매우 커지는 상황(무한대에 가까워질 때)**을 상정한다. 이를 점근적(Asymptotic) 분석이라 하며, 다음과 같은 특징이 있다:덜 중요한 항은 무시한다예: f(n) = 2n² + 3n + 1 → 점근적으로 n²만 남는다.계수도 무시한다예: f(n) = 100n² → O(n²)로 표현한다..
CS지식/알고리즘 (Algorithm) 2025. 4. 26. 01:38
이전 Prev 1 Next 다음