데이터 구조 시간 복잡도

시간 복잡도란 무엇인가요?

알고리즘의 특정 함수에는 T(n)으로 표시되는 n개의 기본 연산이 반복됩니다. 이제 특정 보조 함수 f(n)가 있으므로 n이 무한대에 가까워지면 T(n)/f( 극한이 됩니다. n)의 값이 0이 아닌 상수인 경우 f(n)은 T(n)과 동일한 크기 차수의 함수라고 하며 T(n)=O(f(n)으로 기록됩니다. ), O(f(n))이라고 불리는 알고리즘의 점근적 시간 복잡도를 시간 복잡도라고 합니다.

일반적인 용어로 소위 시간 복잡도는 n이 계속 증가함에 따라 이 알고리즘의 추세를 나타내는 동일한 곡선 유형의 함수 f(n)를 찾는 것입니다. 입력량 n이 점차 증가할 때 시간 복잡도의 한계 상황을 알고리즘의 "점근적 시간 복잡도"라고 합니다.

시간 복잡도 계산 방법:

1. 실행 시간의 모든 추가 상수를 상수 1

2으로 대체합니다. 수정된 실행 시간 함수에서는 가장 높은 차수 항만 유지됩니다.

3. 가장 높은 순서 항의 계수

는 크기가 증가하는 순서로 정렬됩니다. 일반적인 시간 복잡성은 다음과 같습니다.

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