알고리즘의 시간 복잡도와 공간 복잡도

알고리즘 복잡성이란 알고리즘이 실행 가능한 프로그램에 작성된 후 이를 실행하는 데 필요한 리소스를 의미합니다. 리소스에는 시간 리소스와 메모리 리소스가 포함됩니다. 수학과 컴퓨팅 입문에 적용.

알고리즘 시간 복잡도 정의: (권장 학습: PHP 비디오 튜토리얼)

알고리즘을 분석할 때 문장 T(n)의 총 실행 횟수는 문제 크기 n의 함수입니다. , 그리고 n에 따른 T(n)의 변화를 분석하고 T(n)의 크기 순서를 결정합니다. 알고리즘의 시간 복잡도, 즉 알고리즘의 시간 측정은 다음과 같이 작성됩니다. T(n) = O(f(n)). 이는 문제 크기 n이 커질수록 알고리즘 실행 시간의 증가율이 f(n)의 증가율과 동일하다는 것을 의미하는데, 이를 알고리즘의 점근적 시간 복잡도라고 하며, 이를 시간 복잡도라고 합니다. 여기서 f(n)은 문제 크기 n의 함수입니다.

대문자 O()를 사용하여 Big O 표기법이라고 하는 알고리즘의 시간 복잡도를 반영합니다.

다양한 알고리즘에서 알고리즘의 명령문 실행 횟수가 일정할 경우 시간 복잡도는 O(1)입니다. 또한 시간 빈도가 다른 경우 시간 복잡도는 T( n )=n^2+3n+4 및 T(n)=4n^2+2n+1 은 서로 다른 주파수를 갖지만 시간 복잡도는 동일하며 둘 다 O(n^2)입니다.

크기가 증가하는 순서로 배열하면 일반적인 시간 복잡도는 다음과 같습니다.

상수 순서 O(1), 로그 순서 O(log2n)(밑이 2인 n의 로그, 아래와 동일), 선형 순서 O(n),

1차 대수 차수 O(nlog2n), 제곱 차수 O(n^2), 3차 차수 O(n^3),...,

k번째 거듭제곱 차수 O(n^k), 지수 차수 O(2^n) ). 문제 크기 n이 계속 증가함에 따라 위의 시간 복잡도는 계속 증가하고 알고리즘의 실행 효율성은 낮아지게 됩니다.

알고리즘 공간 복잡도

시간 복잡도와 마찬가지로 공간 복잡도는 컴퓨터 내에서 알고리즘이 실행될 때 필요한 저장 공간을 측정한 것입니다.

는 다음과 같이 기록됩니다.

S(n)=O(f(n))

알고리즘 실행 중에 필요한 저장 공간은 3가지 부분으로 구성됩니다.

알고리즘 프로그램이 차지하는 공간

초기 입력; 데이터가 차지하는 저장 공간

알고리즘 실행 중에 추가 공간이 필요합니다.

많은 실제 문제에서는 알고리즘이 차지하는 저장 공간을 줄이기 위해 일반적으로 압축 저장 기술이 사용됩니다.

PHP 관련 기술 기사를 더 보려면 PHP 그래픽 튜토리얼 칼럼을 방문하여 알아보세요

위 내용은 알고리즘의 시간 복잡도와 공간 복잡도의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!