알고리즘 복잡성에는 주로 무엇이 포함됩니까?

알고리즘 복잡도:

시간 복잡도

컴퓨터 과학에서 시간 복잡도는 시간 복잡도라고도 알려져 있으며, 알고리즘의 시간 복잡도는 알고리즘의 실행 시간을 질적으로 설명하는 함수입니다. 이는 알고리즘에 대한 입력 값을 나타내는 문자열 길이의 함수입니다. 시간 복잡도는 이 함수의 하위 항과 선행 계수를 제외하고 빅 O 표기법으로 표현되는 경우가 많습니다. 이 접근 방식을 사용하면 시간 복잡도는 점근적이라고 할 수 있습니다. 즉, 입력 값의 크기가 무한대에 가까워집니다.

시간 복잡도를 계산하기 위해 일반적으로 알고리즘의 연산 단위 수를 추정하며, 각 단위의 실행 시간은 동일합니다. 따라서 알고리즘의 총 실행 시간과 작동 단위 수는 기껏해야 일정한 요소만큼 다릅니다.

동일한 크기의 서로 다른 입력 값으로 인해 여전히 알고리즘의 실행 시간이 달라질 수 있으므로 일반적으로 최대 실행 시간으로 정의되는 T(n)으로 표시되는 알고리즘의 최악의 복잡성을 사용합니다. 모든 크기의 입력 n에 필요합니다. 덜 일반적으로 사용되는 또 다른 방법은 평균 사례 복잡성으로, 일반적으로 지정된 경우에만 사용됩니다. 시간 복잡도는 함수 T(n)의 자연적인 특성에 따라 분류될 수 있습니다. 예를 들어, T(n) =O(n)인 알고리즘을 "선형 시간 알고리즘"이라고 합니다. ^n) 및 M= O(T(n)), M≥n> 1인 알고리즘을 "지수 시간 알고리즘"이라고 합니다.

알고리즘에 걸리는 시간은 알고리즘의 명령문 실행 횟수에 비례합니다. 더 많은 명령문이 실행되는 알고리즘은 더 많은 시간이 걸립니다. 알고리즘의 명령문 실행 횟수를 명령문 빈도 또는 시간 빈도라고 합니다. 이를 T(n)으로 표시합니다.
　일반적인 상황에서 알고리즘의 기본 연산 반복 실행 횟수는 문제 크기 n의 함수이며, 특정 보조 함수 f(n)가 있는 경우 n이 무한대에 가까워지면 T가 됩니다. (n)/f(n)의 극한값이 0이 아닌 상수인 경우 f(n)은 T(n)과 동일한 크기 차수의 함수라고 합니다. T(n)=O(f(n))으로 표시되는 O(f(n))은 알고리즘의 점근적 시간 복잡도, 줄여서 시간 복잡도라고 합니다.
　 다양한 알고리즘 중 알고리즘의 명령문 실행 횟수가 일정할 경우 시간 복잡도는 O(1)입니다. 또한, 시간 빈도가 다른 경우에는 T(n)과 같이 시간 복잡도가 동일할 수 있습니다. ) =n2+3n+4 및 T(n)=4n2+2n+1은 서로 다른 주파수를 갖지만 시간 복잡도는 동일하며 둘 다 O(n2)입니다.

시간 빈도

알고리즘을 실행하는 데 걸리는 시간은 이론적으로 계산할 수 없습니다. 컴퓨터에서 테스트를 실행해야만 알 수 있습니다. 그러나 우리가 모든 알고리즘을 컴퓨터에서 테스트하는 것은 불가능하고 불필요합니다. 우리는 어떤 알고리즘이 더 많은 시간이 걸리고 어떤 알고리즘이 더 적은 시간이 걸리는지만 알면 됩니다. 그리고 알고리즘에 걸리는 시간은 알고리즘의 명령문 실행 횟수에 비례합니다. 더 많은 명령문이 실행되는 알고리즘은 더 많은 시간이 걸립니다. 알고리즘의 명령문 실행 횟수를 명령문 빈도 또는 시간 빈도라고 합니다. 이를 T(n)으로 표시합니다.

공간 복잡도

시간 복잡도와 마찬가지로 공간 복잡도는 컴퓨터 내에서 알고리즘을 실행할 때 필요한 저장 공간을 측정하는 것을 의미합니다. 다음과 같이 기록됨:

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

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

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

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

• 알고리즘 실행 중에 필요한 추가 공간.

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

위 내용은 알고리즘 복잡성에는 주로 무엇이 포함됩니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!