알고리즘의 시간 복잡도와 공간 복잡도에 대해 이야기하는 기사

이 글에서는 알고리즘에 대해 알아보고 알고리즘의 시간 복잡도와 공간 복잡도에 대해 소개하겠습니다. 모든 분들께 도움이 되길 바랍니다!

알고리즘은 데이터를 조작하고 프로그램 문제를 해결하는 데 사용되는 일련의 방법을 나타냅니다. 동일한 문제에 대해 다른 알고리즘을 사용하면 최종 결과는 동일할 수 있지만 프로세스에 소요되는 리소스와 시간은 매우 다릅니다.

그렇다면 다양한 알고리즘의 장단점을 어떻게 측정해야 할까요?

주로 알고리즘이 차지하는 "시간"과 "공간"이라는 두 가지 차원에서 생각해 보세요.

• 시간 차원: 현재 알고리즘을 실행하는 데 소요되는 시간을 의미하며 이를 설명하기 위해 일반적으로 "시간 복잡도"를 사용합니다.

• 공간 차원: 현재 알고리즘을 실행하는 데 필요한 메모리 공간을 나타냅니다. 이를 설명하기 위해 일반적으로 "공간 복잡성"을 사용합니다.

따라서 알고리즘의 효율성을 평가하는 것은 주로 시간 복잡도와 공간 복잡도에 따라 달라집니다. 하지만 때로는 시간과 공간이 '케이크를 먹고, 케이크도 먹어라'고 둘 다 가질 수 없기 때문에 균형점을 찾아야 합니다.

"시간 복잡도"와 "공간 복잡도"의 계산 방법을 각각 소개하겠습니다.

1. 시간 복잡도

알고리즘의 "시간 복잡도"를 알고 싶습니다. 많은 사람들이 가장 먼저 생각하는 방법은 알고리즘 프로그램을 한 번 실행해 보면 자연스럽게 소모되는 시간을 알 수 있습니다.

이 방법 괜찮나요? 물론 가능하지만 단점도 많습니다.

이 방법은 작동 환경의 영향을 받기 쉽습니다. 고성능 시스템에서 실행한 결과는 저성능 시스템에서 실행한 결과와 매우 다릅니다. 그리고 이는 테스트에 사용되는 데이터의 규모와도 많은 관련이 있습니다. 게다가 우리가 알고리즘을 작성했을 때에도 이를 완전히 실행할 수 있는 방법이 없었습니다.

따라서 또 다른 좀 더 일반적인 방법이 나옵니다: " Big O 표기법", 즉 T(n) = O(f(n))

먼저 예를 살펴보겠습니다.

for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

By " Big O 표기법", 이 코드의 시간 복잡도는 O(n), 왜?

Big O 표기법에서 시간 복잡도 공식은 다음과 같습니다. T(n) = O( f(n) ), 여기서 f(n)은 각 코드 줄이 실행되는 횟수의 합을 나타내고 O는 비례 관계를 나타냅니다. 이 공식의 전체 이름은 알고리즘의 점근적 시간 복잡도입니다.

위의 예를 계속해서 살펴보겠습니다. 각 코드 줄의 실행 시간은 1개의 입자 시간을 사용하여 표현합니다. 그러면 이 예의 첫 번째 줄은 1개의 입자 시간이 소요됩니다. 세 번째 줄의 실행 시간은 1 입자 시간이고, 네 번째 줄의 실행 시간도 n 입자 시간입니다(두 번째와 다섯 번째 줄은 기호이므로 지금은 무시하세요). 그러면 총 시간은 1 입자 시간입니다. + n 입자 시간 + n 입자 시간, 즉 (1 +2n) 입자 시간, 즉 T(n) = (1+2n)*입자 시간 이 결과로부터 이의 시간 소모를 알 수 있습니다. 알고리즘은 n의 변화에 ​​따라 변경됩니다. 따라서 이 알고리즘의 시간 복잡도를 다음과 같이 단순화할 수 있습니다. T(n) = O(n)

큰 O 표기법을 사용하지 않기 때문에 왜 이렇게 단순화할 수 있습니까? 알고리즘의 실행 시간을 실제로 나타내기 위해 사용됩니다. 코드 실행 시간의 증가 추세를 나타내는 데 사용됩니다.

그래서 위의 예에서 n이 무한하다면 T(n) = time(1+2n)의 상수 1은 의미가 없고 배수 2도 의미가 없습니다. 따라서 간단히 T(n) = O(n)으로 단순화할 수 있습니다. Common 시간 복잡성 지표는 다음과 같습니다.

제곱 순서 O(n²)

• 입방 순서 O(n³)

• K번째 순서 O(n^k)

• 지수 순서(2^n)

• 시간 복잡도 위에서 아래로의 크기가 점점 커지고 실행 효율성도 점점 낮아지고 있습니다.
• 다음은 설명하기 위해 더 일반적으로 사용되는 몇 가지를 선택합니다(엄격한 순서는 아님):

• 일정한 순서 O(1)
• 몇 줄의 코드가 실행되더라도 상관 없습니다. 루프와 같은 복잡한 구조가 없는 한 이 코드의 시간 복잡도는 다음과 같이 O(1)입니다.

  int i = 1;
  int j = 2;
  ++i;
  j++;
  int m = i + j;

  위 코드가 실행될 때 특정 변수의 증가에 따라 소비가 증가하지 않습니다. 따라서 이런 종류의 코드가 아무리 길어도 수만 줄, 수십만 줄이더라도 시간 복잡도는 O(1)로 표현할 수 있습니다.

선형 순서 O(n)

• 이 내용은 첫 번째 코드 예제에서 다음과 같이 설명되었습니다.

  for(i=1; i<=n; ++i)
  {
     j = i;
     j++;
  }

  이 코드에서 for 루프의 코드는 n번 실행됩니다. 따라서 n이 변경됨에 따라 소비하는 시간도 변경되므로 이러한 유형의 코드는 O(n)을 사용하여 시간 복잡도를 나타낼 수 있습니다.

대수 순서 O(logN)

• 먼저 코드를 살펴보겠습니다.

  int i = 1;
  while(i<n)
  {
      i = i * 2;
  }

  从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。我们试着求解一下，假设循环x次之后，i 就大于 2 了，此时这个循环就退出了，也就是说 2 的 x 次方等于 n，那么 x = log2^n

  也就是说当循环 log2^n 次以后，这个代码就结束了。因此这个代码的时间复杂度为：O(logn)

  • 线性对数阶O(nlogN)

  线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为O(logn)的代码循环N遍的话，那么它的时间复杂度就是 n * O(logN)，也就是了O(nlogN)。

  就拿上面的代码加一点修改来举例：

  for(m=1; m<n; m++)
  {
      i = 1;
      while(i<n)
      {
          i = i * 2;
      }
  }

  • 平方阶O(n²)

  平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。

  举例：

  for(x=1; i<=n; x++)
  {
     for(i=1; i<=n; i++)
      {
         j = i;
         j++;
      }
  }

  这段代码其实就是嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)

  如果将其中一层循环的n改成m，即：

  for(x=1; i<=m; x++)
  {
     for(i=1; i<=n; i++)
      {
         j = i;
         j++;
      }
  }

  那它的时间复杂度就变成了 O(m*n)

  • 立方阶O(n³)、K次方阶O(n^k)

  参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

  除此之外，其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法，有点复杂，这里就不展开了。

  二、空间复杂度

  既然时间复杂度不是用来计算程序具体耗时的，那么我也应该明白，空间复杂度也不是用来计算程序实际占用的空间的。

  空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度，同样反映的是一个趋势，我们用 S(n) 来定义。

  空间复杂度比较常用的有：O(1)、O(n)、O(n²)，我们下面来看看：

  • 空间复杂度 O(1)

  如果算法执行所需要的临时空间不随着某个变量n的大小而变化，即此算法空间复杂度为一个常量，可表示为 O(1)

  举例：

  int i = 1;
  int j = 2;
  ++i;
  j++;
  int m = i + j;

  代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)

  • 空间复杂度 O(n)

  我们先看一个代码：

  int[] m = new int[n]
  for(i=1; i<=n; ++i)
  {
     j = i;
     j++;
  }

  这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)

  以上，就是对算法的时间复杂度与空间复杂度基础的分析，欢迎大家一起交流。

  更多算法相关知识，请访问：编程入门！！

위 내용은 알고리즘의 시간 복잡도와 공간 복잡도에 대해 이야기하는 기사의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!