컴퓨터 공학/알고리즘

알고리즘 복잡도와 점화식: 개념과 성능 평가

1. 복잡도(Complexity)란?알고리즘의 복잡도는 작성한 알고리즘이 얼마나 복잡한지를 평가하는 기준이다. 일반적으로 알고리즘의 성능을 분석할 때 시간복잡도와 공간복잡도를 고려한다. 1.1 시간복잡도(Time Complexity)시간복잡도는 프로그램의 실행 시간이 입력 크기에 따라 어떻게 변화하는지를 나타내는 척도이다. 이는 알고리즘이 수행하는 연산의 개수를 기반으로 측정된다. 1.2 공간복잡도(Space Complexity)공간복잡도는 알고리즘이 실행되는 동안 필요한 메모리 공간의 양을 의미한다. 이는 프로그램이 실행될 때 유지해야 하는 변수, 데이터 구조, 호출 스택 등의 크기에 의해 결정된다.  2. 차수와 Big O 표기법알고리즘의 수행 시간은 기본 연산의 빈도수에 의해 결정되며, 이를 차수(..

2025. 3. 17. 19:48

컴퓨터 공학/알고리즘

[알고리즘] 시간복잡도와 빅오(Big O), 오메가($\Omega$) 표기법

시간 복잡도란?시간 복잡도란 알고리즘의 성능을 나타내는 지표로 입력횟수에 대한 연산 횟수 상한을 의미합니다. 따라서 시간 복잡도가 낮을 수록 연산 횟수가 줄어들고 효율적인 알고리즘이 됩니다.  알고리즘 시간 측정 방법알고리즘의 성능 측정을 위해서는 2가지의 측정 방법이 있는데 하나는 절대 시간을 측정하는 방법이고 하나는 시간복잡도를 측정하는 것이다.   절대 시간 측정말 그대로 프로세스가 실행되고 종료되는 시간을 측정하는 것이다. 그런데 이 방식의 문제는 실행환경에 따라서 결과 값이 달라진다는 것이다. 그래서 코딩 테스트와 같은 환경에서 사용은 부적합하다.   시간 복잡도 측정이 방식은 연산 횟수를 바탕으로 시간을 표현한다. 그래서 실행환경에 따른 차이 없이 동일하게 측정이 가능하다. 시간 복잡도를 나태..

2024. 7. 11. 19:32