기술나눔

[수작업으로 파쇄된 데이터 구조] 방어구 제거/공간 복잡도

2024-07-12

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

목차

머리말

공간/시간 복잡도가 무엇인지 알고 싶다면 데이터 구조가 무엇인지 알아야 합니다.

이는 두 가지 수준에서 이해될 수 있습니다. Douyin을 주제로 화제가 되는 국제 행사, Yongzheng의 갑옷 제거 등 데이터는 우리 생활 곳곳에 존재합니다. 우리 사용자가 볼 수 있는 것은 Douyin이 백엔드 서버에 저장하는 데이터입니다. 그러나 이러한 데이터는 모두 하나의 특징을 가지고 있습니다. 즉, 모두 Douyin의 핫 검색 목록에 있으며 이 목록은 사용자가 검색할 수 있도록 데이터가 고정된 위치에 있도록 구성되어 있습니다.

또한 데이터 구조에서는 알고리즘이 분리될 수 없습니다. 방금 말했듯이 데이터 구조는 데이터를 구조에 정기적으로 저장하므로 구조에서 데이터에 효율적으로 액세스하는 방법은 알고리즘입니다.

시간 복잡도

알고리즘에는 시간 복잡도와 공간 복잡도가 있습니다. 컴퓨터의 메모리 용량이 점점 커지고 있기 때문에 공간 복잡도보다 시간 복잡도가 더 중요합니다.그럼 먼저 시간복잡도를 알아볼까요?

개념

시간 복잡도, 가장 중요한 단어는 시간입니다. 여기서 시간은 프로그램이 실행되는 시간을 의미합니다. 시간 복잡도가 낮을수록 알고리즘이 더 나은 것으로 입증됩니다.시간복잡도 계산은 함수식 T(N)으로 표현됩니다.

그렇다면 이 프로그램의 시간복잡도를 미리 계산하여 최적의 솔루션을 위한 코드를 작성해 보는 것은 어떨까요? 여기에는 컴퓨터 문제가 포함됩니다.

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

코드를 살펴보겠습니다.

// 请计算⼀下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

count의 실행 횟수를 기준으로 이 코드를 살펴보면 다음과 같아야 합니다.
T(N) = N2 + 2 * N + 10
• N = 10 T(N) = 130
• N = 100 T(N) = 10210
• N = 1000 T(N) = 1002010

이때 누군가가 int count=0이 계산되지 않는다고 말하더군요.

여기서 우리는 컴퓨터의 CPU가 초당 수억 번 실행될 수 있다는 점을 너무 과소평가합니다. 물론 이 짧은 시간은 무시할 수 있습니다. 따라서 우리가 계산한 시간 복잡도는 정확하지 않으며 단지 대략적인 추정일 뿐입니다. 이때 이를 표현하기 위해 새로운 기호를 사용합니다.

Big O의 점근적 표현

Big O 표기법: 함수의 점근적 동작을 설명하는 데 사용되는 수학적 기호로, 여기서는 추정된 시간 복잡도를 나타내는 데 사용됩니다.

그렇다면 여기서는 여전히 T(N)처럼 계산됩니까? 그렇다면 이를 표현하기 위해 다른 기호를 사용할 필요가 없습니다. 여기에는 O 계산 규칙이 포함됩니다.

  1. 시간복잡도 함수식 T(N)에서는 N이 계속 증가하면 하위 항이 결과에 미치는 영향이 점점 작아지기 때문에 최고 차항만 유지되고 하위 항은 제거됩니다. N이 무한할 경우 무시할 수 있습니다.
  2. 최고차 항이 존재하고 1이 아닌 경우 N이 계속 증가함에 따라 이 계수는 결과에 점점 더 적은 영향을 미치므로 이 항의 상수 계수를 제거합니다. N이 무한할 때 무시할 수 있습니다.
  3. T(N)에 N 관련 항목이 없고 상수 항목만 있는 경우 모든 덧셈 상수를 상수 1로 바꿉니다.

그런 다음 위의 T(N)=N^ 2 + 2 * N + 10을 살펴보세요. 여기서 가장 높은 차수는 N2이므로 다른 낮은 차수를 제거하면 복잡도는 (ON^2)입니다.

소형 다지기

// 计算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

여기서 T(N)=M+N, 다시 O(N)을 계산해 보겠습니다. 여기서 M과 N은 모두 동일한 순서이므로 첫 번째 규칙을 따르지 않으며 두 번째 및 세 번째 규칙에도 해당하지 않습니다. , 그래서 o(N+M), 그러면 누군가 N이 M보다 크면 O(N)이어야 하는지 물었습니다. 여기서 질문은 N이 M보다 크다는 것을 어떻게 알 수 있느냐는 것입니다. M이 N보다 크다면 어떻게 될까요? 그래서 우리는 안전을 위해 여기에 머물게 됩니다.

// 计算strchr的时间复杂度？
const char * strchr ( const char
 * str, int character)
{
const char* p_begin = s;
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
  • 12
  • 13

여기서는 str에서 문자의 위치를 ​​찾고 있습니다. 여기에 지식 포인트를 추가하겠습니다.

  • 우리의 O 계산은 일반적으로 알고리즘의 최악의 복잡성입니다.
    여기서는 세 가지 수준의 복잡성으로 나눌 수 있습니다.
    1. 최선의 시나리오
    문자열의 첫 번째 위치에서 문자를 찾으려면 다음을 수행하십시오.
    F(N) = 1, 복잡도는 o(1)입니다.

2. 평균 상황:
문자열 중간에서 문자를 찾으려면 다음을 수행하십시오.
F(N) = N/2, O(N/2)

3. 최악의 시나리오
문자열의 마지막 위치에서 문자를 찾으려면 다음을 수행하십시오.
F(N) = N,O(N)

// 计算BubbleSort的时间复杂度？
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
  • 19

여기에 이미지 설명을 삽입하세요.
최악의 경우 높은 차수를 유지하고 n/2를 제거(첫 번째 항목)하고 계수(두 번째 항목)를 무시하므로 ON^2입니다.

void func5(int n)
{
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
}
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

n=2일 때 실행 횟수는 1입니다.
n=4인 경우 실행 횟수는 2입니다.
n=16일 때 실행 횟수는 4입니다.
실행 횟수를 x라고 가정하면 2가 됩니다.
x = 이다
따라서 실행 횟수: x = log n
따라서 func5의 최악의 시간 복잡도는 다음과 같습니다.
N(로그2^n)

책마다 표현 방법이 다릅니다. 위의 작성 방법은 크게 다르지 않습니다.

공간 복잡도

공간 복잡도에 대해 주목해야 할 점은 계산 표현도 O로 표시되며, 그 규칙은 시간 복잡도와 동일한 세 가지 규칙을 따른다는 것입니다.

알아채다

함수가 실행될 때 필요한 스택 공간(매개변수, 지역 변수, 일부 레지스터 정보 등 저장)은 컴파일 중에 결정되므로 공간 복잡도는 주로 함수가 실행될 때 명시적으로 적용되는 추가 공간에 의해 결정됩니다. .

예 1:

// 计算BubbleSort的时间复杂度？
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
  • 19

함수 스택 프레임은 컴파일 중에 결정되었습니다.
런타임 중에 함수가 요청하는 추가 공간에만 주의하면 됩니다.
BubbleSort의 추가 적용 공간은
일정한 양의 추가 공간을 사용하는 교환과 같은 제한된 수의 지역 변수가 있습니다.
따라서 공간 복잡도는 O(1)입니다.

개인 프로필

그는 30년 이상 기술 연구에 전념해 왔으며, java, linux, javascript, php, css 등 다양한 언어에 능숙하며, 오픈 소스 분야에서 많은 공헌을 했습니다. 나중에 참조할 수 있도록 기술 개발의 일부 문제를 공유하는 개발자 문서 스테이션입니다.

내 연락처 정보

우편