Java 데이터 구조의 수집 프레임워크와 일반적인 알고리즘은 무엇입니까?

1 컬렉션 프레임워크

1.1 컬렉션 프레임워크 개념

Java 컬렉션 프레임워크 컨테이너 컨테이너라고도 알려진 Java 컬렉션 프레임워크는 java.util 패키지에 정의된 인터페이스 및 구현 클래스 집합입니다.

주요 성능은 하나의 단위에 여러 요소를 배치하는 것인데, 이러한 요소를 빠르고 편리하게 저장, 검색, 관리하는 데 사용되며 흔히 CRUD라고 합니다.

클래스 및 인터페이스 개요:

1.2 컨테이너와 관련된 데이터 구조

Collection: 대부분의 컨테이너에서 일반적으로 사용되는 일부 메서드가 포함된 인터페이스

List: ArrayList 및 LinkedList의 요구 사항을 표준화하는 인터페이스 구현 방법

• ArrayList: List 인터페이스 구현, 하단 레이어는 동적 유형 시퀀스 테이블

• LinkedList: List 인터페이스 구현, 하단 레이어는 이중 연결 리스트

Stack: 하단 레이어 는 스택이고 스택은 특수한 시퀀스 테이블입니다.

Queue: 맨 아래 레이어는 큐이고, 큐는 특수한 시퀀스 테이블입니다.

Deque: 인터페이스입니다.

Set: 집합입니다. 인터페이스이고 K 모델이 그 안에 배치됩니다.

• HashSet: 맨 아래 레이어는 Hash bucket이고 쿼리의 시간 복잡도는 O(1)

• TreeSet: 맨 아래 레이어는 red-black입니다. 트리에서 쿼리의 시간 복잡도는 O()이며 키 순서에 대해

Map: mapping, inside 저장된 것은 K-V 모델의 키-값 쌍입니다

• HashMap: 맨 아래 레이어는 해시 버킷이고 쿼리 시간 복잡도는 O(1)

• TreeMap: 맨 아래 레이어는 레드-블랙 트리이고 쿼리 시간 복잡도는 O( )입니다. 키 순서

2 알고리즘

2.1 알고리즘 개념

알고리즘(Algorithm): 하나 또는 하나의 값 그룹을 입력으로 사용하고 하나 또는 하나의 값 그룹을 출력으로 생성하는 잘 정의된 계산 프로세스입니다. 알고리즘은 입력 데이터를 출력 결과로 변환하도록 설계된 일련의 계산 단계입니다.

2.2 알고리즘 효율성

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

3 시간 복잡도

3.1 시간 복잡도의 개념

시간 복잡도는 알고리즘의 실행 시간을 나타내는 컴퓨터 과학의 수학적 함수로, 알고리즘의 시간 효율성을 정량적으로 설명합니다. 알고리즘의 실행 시간은 이론적으로 계산할 수 없습니다. 소요 시간은 프로그램이 실제로 컴퓨터에서 실행된 후에만 알 수 있습니다. 각 알고리즘을 컴퓨터에서 테스트할 수 있지만 이는 매우 번거롭기 때문에 시간 복잡도를 통해 분석하는 방법이 있습니다. 알고리즘의 시간 복잡도는 명령문의 개수를 실행하는 데 걸리는 시간에 비례하고, 시간 복잡도는 알고리즘의 기본 연산 실행 횟수에 따라 달라집니다.

3.2 Big O의 점근 표기법

// 请计算一下func1基本操作执行了多少次？
void func1(int N){
	int count = 0;
	for (int i = 0; i < N ; i++) {
		for (int j = 0; j < N ; j++) {
			count++;
		}
	}
	for (int k = 0; k < 2 * N ; k++) {
		count++;
	} 
	int M = 10;
	while ((M--) > 0) {
		count++;
	} 
	System.out.println(count);
}

Func1이 수행하는 기본 연산 수: F(N)=N^2+2*N+10

• N = 10 F(N) = 130

• N = 100 F(N) = 10210

• N = 1000 F(N) = 1002010

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

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

3.3 Big O 순서 방법 파생

• 실행 시간의 모든 덧셈 상수를 상수 1로 바꿉니다.

• 수정된 런타임 기능에서는 가장 높은 순서의 항만 유지됩니다.

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

big O의 점근적 표현을 사용한 후 Func1의 시간 복잡도는 다음과 같습니다. O(n^2)

• N = 10 F(N) = 100

• N = 100 F(N) = 10000

• N = 1000 F(N) = 1000000

위를 통해 Big O 점근 표기법에서는 결과에 거의 영향을 미치지 않는 항을 제외하여 실행 빈도를 간결하고 명확하게 표현하고 있음을 알 수 있습니다. . 또한 일부 알고리즘의 시간 복잡도에는 최고, 평균 및 최악의 경우가 있습니다.

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

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

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

예: 데이터 검색

平均情况：N/2次找到

在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

4 空间复杂度

对于一个算法而言，空间复杂度表示它在执行期间所需的临时存储空间大小。空间复杂度的计算方式并非程序所占用的字节数量，因为这并没有太大的意义；实际上，空间复杂度的计算基于变量的数量。大O渐进表示法通常用来计算空间复杂度，其计算规则类似于实践复杂度的计算规则。

实例1:

// 计算bubbleSort的空间复杂度？
void bubbleSort(int[] array) {
	for (int end = array.length; end > 0; end--) {
		boolean sorted = true;
		for (int i = 1; i < end; i++) {
			if (array[i - 1] > array[i]) {
				Swap(array, i - 1, i);
				sorted = false;
			}
		} 
		if(sorted == true) {
		break;
		}
	}
}

实例2:

// 计算fibonacci的空间复杂度？
int[] fibonacci(int n) {
	long[] fibArray = new long[n + 1];
	fibArray[0] = 0;
	fibArray[1] = 1;
	for (int i = 2; i <= n ; i++) {
		fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
	} 
	return fibArray;
}

实例3:

// 计算阶乘递归Factorial的空间复杂度？
long factorial(int N) {
	return N < 2 ? N : factorial(N-1)*N;
}

• 实例1使用了常数个额外空间，所以空间复杂度为 O(1)

• 实例2动态开辟了N个空间，空间复杂度为 O(N)

• 实例3递归调用了N次，开辟了N个栈帧，每个栈帧使用了常数个空间。空间复杂度为O(N)

위 내용은 Java 데이터 구조의 수집 프레임워크와 일반적인 알고리즘은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!