Java 시간 복잡도 및 공간 복잡도 예제 분석

1. 알고리즘 효율성

알고리즘 효율성 분석은 두 가지 유형으로 나누어집니다. 첫 번째는 시간 효율성이고, 두 번째는 공간 효율성입니다. 시간 효율성을 시간 복잡도, 공간 효율성을 공간 복잡도라고 합니다. 시간 복잡도는 주로 알고리즘의 실행 속도를 측정하는 반면, 공간 복잡도는 주로 알고리즘에 필요한 추가 공간을 측정합니다. 컴퓨터 개발 초기에는 컴퓨터의 저장 용량이 매우 작았습니다. 그래서 우리는 공간 복잡도에 많은 관심을 갖고 있습니다. 그러나 컴퓨터 산업의 급속한 발전 이후 컴퓨터의 저장 용량은 매우 높은 수준에 도달했습니다. 따라서 우리는 더 이상 알고리즘의 공간 복잡도에 특별한 주의를 기울일 필요가 없습니다.

2. 시간 복잡도

1. 시간 복잡도의 개념

알고리즘의 기본 연산 실행 횟수는 알고리즘의 시간 복잡도에 비례합니다. 즉, 우리가 코드를 얻어서 코드의 시간복잡도를 살펴보면, 그 코드에서 가장 많이 실행된 문장이 있는 코드가 몇 번이나 실행되었는지를 주로 알아낸다.

2. Big O의 점근적 표현

그림을 보고 분석해 보세요.

N의 값이 점점 커지면 2N과 10의 값은 무시할 수 있습니다.

사실 시간 복잡도를 계산할 때 실제로는 정확한 실행 횟수를 계산할 필요가 없고 대략적인 실행 횟수만 계산하므로 여기서는 Big O의 점근 표현을 사용합니다.

Big O 표기법: 함수의 점근적 동작을 설명하는 데 사용되는 수학 기호입니다.

1. 런타임의 모든 추가 상수를 상수 1로 바꿉니다.

2. 수정된 실행 시간 기능에서는 가장 높은 순서의 항만 유지됩니다.

3. 최고차 항이 존재하고 1이 아닌 경우 이 항을 곱한 상수를 제거합니다. 결과는 Big O 순서입니다.

위를 통해 Big O의 점근적 표현은 결과에 거의 영향을 미치지 않는 항목을 제거하고 실행 횟수를 간결하고 명확하게 표현한다는 것을 알 수 있습니다.

또한 일부 알고리즘의 시간 복잡도에는 최고, 평균 및 최악의 경우가 있습니다.

최악의 경우: 모든 입력 크기에 대한 최대 실행 수(상한)

평균 사례: 다음에 대한 예상 실행 수 모든 입력 크기

최상의 사례: 모든 입력 크기에 대한 최소 실행 수(하한)

예: 데이터 검색 상황: N/2회 발견

실제로 일반적인 상황은 최악의 작동 상황에 중점을 둡니다. 따라서 배열에서 데이터를 검색하는 시간 복잡도는 O(N)

계산 시간 복잡도

예 1:

기본 연산을 2N+10번 도출하여 실행했습니다. O 순서 방법, 우리는 시간 복잡도가 O(N)

이라는 것을 알고 있습니다. 예 2:

기본 연산이 M+N 번 실행되었습니다. 알 수 없는 숫자 M과 N에 대한 시간 복잡도는 다음과 같습니다. O(N+M)

예 3:

기본 연산을 100번 수행합니다. Big O-order 방법을 도출하면 시간 복잡도는 O(1)

예 4: 시간 복잡도를 계산합니다. 버블 정렬의

기본 연산은 최대 N 번, 최악의 경우 (N*(N-1))/2 번 실행됩니다. 빅 O 순서 방법 + 시간 복잡도를 도출하여 일반적으로 최악의 경우 시간 복잡도는 O(N^2

예 5: 이진 검색의 시간 복잡도

기본 연산은 잘하면 한 번, 최악이면 O(logN)번 수행되며, 시간 복잡도는 O(logN)ps입니다. : 알고리즘 분석에서 logN은 밑이 2이고 로그가 N이라는 뜻이다. 어떤 곳에서는 lgN이라고 쓴다(logN이 종이접기 검색을 통해 어떻게 계산되는지 설명하는 것이 좋다)(이진 검색은 매번 제외하기 때문이다. Drop) 부적합한 값의 절반, 나머지 값은 두 부분으로 나뉩니다: n/2. 나머지 값은 두 부분으로 나뉩니다: n/2/2 = n/4)

예 6: 계승 재귀의 시간 복잡도를 계산하세요

재귀의 시간 복잡도 = 재귀 횟수 * 각 재귀가 실행되는 횟수

계산과 분석을 통해 기본 연산이 N번 반복된다는 것을 알 수 있으며, 시간 복잡도는 is O(N)

예 7: 피보나치 재귀의 시간 복잡도

계산.

계산 및 분석을 통해 기본 연산은 2^N번 재귀적이며, 시간 복잡도는 O(2^N)인 것으로 나타났습니다.

규칙:

2^0+2^1+2^2+2^3……2^(n-(n-1))

기하수열의 합

a1 첫 번째 항목을 나타내며 q는 2, 1(1-2^n)/-1과 동일하며 이는 2^n+1과 동일하므로 시간 복잡도는 O(2^n)

3입니다.

공간 복잡도는 알고리즘이 작동하는 동안 일시적으로 차지하는 저장 공간의 양을 측정한 것입니다. 공간 복잡도는 프로그램이 차지하는 공간이 몇 바이트인지가 아니라 별로 의미가 없기 때문에 공간 복잡도는 변수의 개수로 계산됩니다. 공간 복잡도 계산 규칙은 기본적으로 실제 복잡도와 유사하며 Big O 점근 표기법도 사용됩니다.

예 1: 버블 정렬의 공간 복잡도 계산

일정한 추가 공간을 사용하므로 공간 복잡도는 O(1)

예 2: 피보나치의 공간 복잡도 계산

동적 개방형 N 공간까지 올리면 공간 복잡도는 O(N)

예 3: 계승 재귀의 공간 복잡도 계산

재귀 호출이 N회 이루어지고 N 스택 프레임이 열리며 각 스택 프레임은 일정한 양을 사용합니다. 공간의. 공간복잡도는 O(N)

위 내용은 Java 시간 복잡도 및 공간 복잡도 예제 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!