기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

1. 알고리즘의 효율성

동일한 알고리즘 문제를 완성하는 과정에는 여러 가지 방법과 방법이 있지만 최종 효과는 동일하고 정확하지만 효율성은 다를 수 있습니다.
같은 장소에서 출발해서 다른 장소에 도착하는 것처럼, 그 장소에 도달하는 방법에는 비행기, 기차, 자가용 등이 있지만... 걸리는 시간도 다르고 경제도 다릅니다.

1. 복잡성의 개념

알고리즘이 실행 가능한 프로그램에 작성된 후 이를 실행하려면 시간 자원과 공간(메모리) 자원이 필요합니다. 따라서 알고리즘의 품질은 일반적으로 시간과 공간, 즉 시간 복잡도와 공간 복잡도라는 두 가지 차원에서 측정됩니다.
시간 복잡도는 주로 알고리즘 실행 속도를 측정하는 반면, 공간 복잡도는 주로 알고리즘을 실행하는 데 필요한 추가 공간을 측정합니다.
컴퓨터 개발 초기에는 컴퓨터의 저장 용량이 매우 작았습니다. 그래서 우리는 공간 복잡도에 많은 관심을 갖고 있습니다. 그러나 컴퓨터 산업의 급속한 발전 이후 컴퓨터의 저장 용량은 매우 높은 수준에 도달했습니다. 이제 우리는 더 이상 알고리즘의 공간 복잡도에 특별한 주의를 기울일 필요가 없습니다.

2. 복잡성의 중요성

어떤 게임을 할 때 휴대폰이 매우 뜨거워지고, 어떤 게임은 플레이해도 뜨거워지지 않습니다. 이는 복잡함과 불가분의 관계로, 제 휴대폰은 간단한 알고리즘을 실행하고 있으며 빠르게 실행됩니다. 알고리즘은 실행하기 복잡하므로 시간을 덜 사용하려면 최대 전력을 활성화해야 하므로 뜨거워집니다.

2. 시간 복잡도

정의: 컴퓨터 과학에서 알고리즘의 시간 복잡도는 알고리즘의 실행 시간을 정량적으로 설명하는 함수식 T(N)입니다. 시간 복잡도는 프로그램의 시간 효율성을 측정하는데, 프로그램의 실행 시간을 계산해 보면 어떨까요?

• 프로그램 실행 시간은 컴파일 환경 및 실행 중인 머신의 구성과 관련되어 있으므로, 예를 들어 알고리즘 프로그램이 기존 컴파일러로 컴파일되거나 새 컴파일러로 컴파일되면 실행 시간은 동일한 머신에서 달라집니다.
• 동일한 알고리즘 프로그램은 기존의 낮은 구성 머신과 새로운 높은 구성 머신을 사용하여 실행 시간이 다릅니다.
• 그리고 시간은 프로그램을 작성한 후에만 테스트할 수 있으며, 프로그램을 작성하기 전에 이론적 사고를 통해 계산하고 평가할 수는 없습니다.

따라서 알고리즘의 시간 할당을 판단할 때 알고리즘을 실행하는 시간은 고려되지 않고 실행된 명령의 개수만 고려됩니다.

사례:

// 请计算⼀下Func1中++count语句总共执⾏了多少
次？
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--)
	{
		++count;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

관찰을 통해:
Func1이 수행하는 기본 작업 수:
T(N)=N²+ 2*N + 10

실제로 시간 복잡도를 계산할 때 프로그램의 정확한 실행 횟수를 계산하지 않습니다. 정확한 실행 횟수를 계산하는 것은 여전히 ​​매우 번거롭습니다(프로그램 코드의 문장마다 컴파일된 명령의 수가 다릅니다). 이), 정확한 실행 횟수를 계산하는 것은 시간 복잡도, 즉 N이 계속 증가할 때의 T(N)의 차이를 계산함에 있어서 알고리즘 프로그램의 성장 수준만을 비교하려고 하기 때문에 별 의미가 없습니다. 위에서는 N이 계속 증가할 때 상수와 하위 항이 결과에 거의 영향을 미치지 않는다는 것을 확인했습니다. 따라서 프로그램이 증가하는 크기를 나타낼 수 있는 대략적인 실행 횟수만 계산하면 일반적으로 복잡성 표현이 사용됩니다. Big O의 점근 표기법.

3. 공간 복잡도

공간 복잡도는 수학적인 표현이기도 하며, 알고리즘 실행 과정에서 알고리즘의 필요로 인해 일시적으로 할당되는 추가 공간입니다.
공간 복잡도는 프로그램이 차지하는 공간의 바이트 수가 아닙니다. 일반적인 상황에서는 각 개체의 크기가 크게 다르지 않으므로 공간 복잡도는 변수 수로 계산됩니다.
공간 복잡도 계산 규칙은 기본적으로 실제 복잡도와 유사하며 Big O 점근 표기법도 사용됩니다.
참고: 함수가 실행될 때 필요한 스택 공간(매개변수, 지역 변수, 일부 레지스터 정보 등 저장)은 컴파일 중에 결정되므로 공간 복잡성은 주로 런타임 중에 함수에 의해 명시적으로 적용되는 추가 공간에 의해 결정됩니다. . 확신하는
공간은 현재 컴퓨터 개발에서 중요한 고려 사항이 아니지만 과도한 낭비는 피해야 합니다. 너무 많은 낭비는 불필요한 문제를 야기합니다.

4. Big O의 점근적 표현

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

• 1. 시간복잡도 함수식 T(N)에서는 N이 계속 증가하면,
  결과에 대한 저차 항의 영향은 점점 작아지고 있으며 N이 무한할 때 무시할 수 있습니다.
• 2. 최고차 항이 존재하고 1이 아닌 경우, N이 계속 증가함에 따라 이 항의 상수 계수를 제거합니다.
  결과에 미치는 영향은 점점 작아지고 있으며 N이 무한대일 때는 무시할 수 있습니다.
• 3. T(N)에 N 관련 항목은 없고 상수 항목만 있는 경우, 덧셈 상수를 모두 상수 1로 대체합니다.

최악의 경우: 모든 입력 크기에 대한 최대 실행 수(상한)
평균 사례: 모든 입력 크기에 대한 예상 실행 수
최선의 경우: 모든 입력 크기에 대한 최소 실행 수(하한)
실제로 Big O의 점근적 표현은 일반적으로 최악의 작동 상황인 알고리즘의 상한에 초점을 맞춥니다.

5. 계산 복잡도 사례

1. 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--)
	{
		++count;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

시간 복잡도:

이 코드는 count=0과 같이 한 번 실행되는 코드를 생략합니다.
실행 시간에 큰 영향을 미치는 코드 실행 횟수 유지
첫 번째 루프의 실행 횟수는 N의 이중 루프 실행입니다.N
두 번째 루프는 루프 실행 횟수 2의 레이어입니다.N
세 번째 주기는 10번입니다.
실행 횟수의 합은 T(N)=N²+2*N+10
Big O는 시간 복잡도를 나타내며, 작은 영향을 버리고 한계를 받아들입니다.
에²)

공간 복잡도:

Func1 함수는 공간 크기에 적용됩니다. 예를 들어 int count = 0이면 int 유형의 공간 크기에 적용됩니다. Int M=10이면 int 유형의 공간에도 적용됩니다.
이 두 공간은 추가 응용 공간 없이 루프에서도 사용됩니다.
응용 공간 크기는 일정합니다.
Big O로 표현되는 공간 복잡도는 다음과 같습니다.
오(1)

2. Fun2의 시간복잡도 계산

void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 2 * N; ++k)
	{
		++count;
	} 
	int M = 10;
	while (M--)
	{
		++count;
	} 
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

시간 복잡도:

코드가 실행되는 횟수는 첫 번째 루프인 N*2보다 큽니다.
두 번째 루프는 10번 실행됩니다.
시간 복잡도를 나타내기 위해 큰 O를 사용합니다. 가장 큰 영향은 2*N입니다. 이전 계수 항은 생략됩니다.
에)

3. Func3의 시간 복잡도 계산

void Func3(int N, int M)
{
	int count = 0;
	for (int k = 0; k < M; ++k)
	{
		++count;
	}
	for (int k = 0; k < N; ++
			k)
	{
		++count;
	}
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

시간 복잡도

두 개의 미지수가 있으며 두 개의 루프에 더 큰 영향을 미칩니다.
첫 번째 루프는 M번 실행됩니다.
두 번째 루프는 N번 실행됩니다.
어느 것이 더 크고 어느 것이 더 작은지는 알 수 없는 숫자일 것입니다.
(M+N)이다.

4. Func4의 시간 복잡도 계산

void Func4(int N)
{
	int count = 0;
	for (int k = 0; k < 100; ++k)
	{
		++count;
	}
	printf("%dn", count);
}
1
2
3
4
5
6
7
8
9

시간 복잡도:

여기서 가장 큰 영향은 순환입니다.
루프 실행 횟수는 100입니다.
고정 상수입니다
오(1)

5. strchr의 시간 복잡도를 계산합니다.

const char* strchr(const char* str, int character)
{
	const char* p_begin = str;
	while (*p_begin != character)
	{
		if(*p_begin == '0')
			return NULL;
		p_begin++;
	}
	return p_begin;
}
1
2
3
4
5
6
7
8
9
10
11

이 함수에 의해 수행되는 기능은 배열에서 문자의 아래 첨자를 찾는 것입니다.
여기서 실행 횟수는 불확실합니다.
F(N)=1을 한 번에 찾는 것이 가능합니다.
중간에 F(N)=N/2 을 찾는 것이 가능합니다.
마지막에 발견될 수도 있고, 발견되지 않으면 NULL을 반환, F(N)=N
Big O는 최악의 시나리오를 취합니다.
시간 복잡도는 O(N)입니다.

6. Func5의 시간 복잡도 계산

void func5(int n)
{
	int cnt = 1;
	while (cnt < n)
	{
		cnt *= 2;
	}
}
1
2
3
4
5
6
7
8

이 실행 횟수는 n의 크기와 관련이 있지만 n번 반복되지는 않습니다. 이는 반복 중에 루프 변수에 2가 곱해지고 루프가 10번 실행된 후 빠르게 튀어나오기 때문입니다. 루프 변수 cnt의 값은 1024에 도달합니다.
사이클 수를 x라고 가정하면 2가 됩니다.^엑스=엔
x=로그인
따라서 시간 복잡도는 O(longn)입니다.

7. BubbleSor의 복잡성 계산

void BubbleSort(int* a, int n)
{
	assert(a);
	for (size_t end = n; end > 0; --end)
	{
		int exchange = 0;
		for (size_t i = 1; i < end; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		} 
		if(exchange == 0)
			break;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

이 기능은 버블 오름차순 정렬을 완료합니다.
여기에 루프가 있습니다. 이 루프는 2단계 중첩 루프입니다.
루프 수는 정의되지 않았습니다.
최악의 시나리오는 외부 루프가 n번 실행되는 것입니다.
그런 다음 내부 루프는 (n-1)+(n-2)+(n-3)+…+2+1+0을 실행합니다.
는 산술수열이고 그 합은 다음과 같습니다.

시간 복잡도는 O(N)입니다.

공간 복잡도:

추가 적용 공간이 없으며, 적용 공간이 일정합니다.
오(1)

8. 계승 재귀 Fac 계산의 복잡성

long long Fac(size_t N)
{
	if (0 == N)
		return 1;
	return Fac(N - 1) * N;
}
1
2
3
4
5
6

시간 복잡도:

N번 반복됨
따라서 시간 복잡도는 O(N)입니다.

공간 복잡도:

재귀할 때마다 공간을 신청해야 합니다.
N번 반복되어 N번의 공간에 적용되었습니다.
공간 복잡도는 O(N)입니다.