실행 시간 (알고리즘)

1. 본문

알고리즘의 실행 시간은 알고리즘 분야나 계산 복잡도 이론에서 어떤 프로그램이 시작하여 종료되기까지 걸리는 시간 길이를 의미합니다.
시간 복잡도

• 정의: 알고리즘의 실행 시간은 입력 값의 크기에 따라 어떻게 변하는지를 나타내는 척도입니다. 시간 복잡도는 알고리즘이 수행하는 연산의 수를 입력 크기의 함수로 표현합니다.
• 표기법: 주로 빅오(Big O) 표기법을 사용하여 시간 복잡도를 나타냅니다. 빅오 표기법은 알고리즘의 최악의 경우 실행 시간을 나타내며, 입력 크기가 무한대로 커질 때 알고리즘의 실행 시간이 어떻게 증가하는지를 보여줍니다.
• O(1): 상수 시간 (Constant Time)
• O(log n): 로그 시간 (Logarithmic Time)
• O(n): 선형 시간 (Linear Time)
• O(n log n): 선형 로그 시간 (Linearithmic Time)
• O(n²): 제곱 시간 (Quadratic Time)
• O(2ⁿ): 지수 시간 (Exponential Time)

• 반복문의 반복 횟수: 반복문이 중첩될수록 실행 시간은 기하급수적으로 증가할 수 있습니다.
• 함수 호출 횟수: 재귀 함수 등 함수 호출이 빈번하게 일어나는 경우, 함수 호출에 따른 오버헤드가 발생할 수 있습니다.
• 특정 행이 수행되는 횟수: 알고리즘 내에서 특정 연산이 얼마나 자주 수행되는지에 따라 실행 시간이 달라질 수 있습니다.

• 시간 복잡도는 알고리즘의 효율성을 평가하는 중요한 지표이지만, 실제 실행 시간과는 차이가 있을 수 있습니다.
• 실제 실행 시간은 하드웨어 성능, 운영체제, 프로그래밍 언어 등 다양한 요인에 의해 영향을 받습니다.