【解密算法:时间与空间的博弈】(中)

简介: 【解密算法:时间与空间的博弈】

【解密算法:时间与空间的博弈】(上):https://developer.aliyun.com/article/1424858


实例三:


// 计算Func4的时间复杂度?
void Func4(int N)
{
  int count = 0;
  for (int k = 0; k < 100; ++k)
  {
    ++count;
  }
  printf("%d\n", count);
}


  1. 循环:for (int k = 0; k < 100; ++k)


这个循环总共执行了 100 次。

循环内部只有一个基本操作 ++count。

因此,总的基本操作数可以表示为:100。


在大O符号表示法中,我们通常关注最高阶的项,而忽略低阶项和常数系数。在这种情况下,最高阶项是 100。

因此,Func4 函数的时间复杂度可以表示为 O(1)。


实例四:


// 计算strchr的时间复杂度?
const char* strchr(const char* str, int character);


strchr 函数用于在给定字符串中查找第一个出现的指定字符,并返回该字符后的部分字符串。


  • 最好情况:1次找到
  • 平均情况:N/2次找到
  • 最坏情况:N次找到


       在一般情况下,strchr 函数的时间复杂度可以被认为是 O(N),其中 N 是输入字符串的长度。这是因为 strchr 需要遍历字符串中的每个字符来查找指定字符。在最坏情况下,它可能需要遍历整个字符串才能找到目标字符。


实例五:


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


BubbleSort 是一种基本的排序算法,其时间复杂度取决于待排序数组的初始状态。让我们分析一下 BubbleSort 的时间复杂度。


       BubbleSort 的主要思想是在每一轮遍历中,比较相邻的两个元素,如果顺序不对就交换它们,直到最大(或最小)元素“冒泡”到正确的位置。在每一轮遍历中,至少会将一个元素放置在其最终的位置上。


       最坏情况下,数组完全逆序,需要执行 N-1 轮比较和交换操作。第一轮中,需要比较和可能的交换 N-1 次;第二轮中,需要比较和可能的交换 n-2次...


       所以,总的操作次数为:(N-1) * N / 2 = N * N / 2 - N / 2


在大O符号表示法中,我们通常关注最高阶的项,而忽略低阶项和常数系数。在这种情况下,最高阶项是 n^2。因此,BubbleSort 的时间复杂度可以表示为 O(n^2)。


       需要注意的是,BubbleSort 的平均和最坏情况下的时间复杂度都是 O(N^2),即使在最好情况下,数组已经是有序的,BubbleSort 也需要进行 n-1 轮比较,时间复杂度都是 O(N)。


实例六:


// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{
  assert(a);
  int begin = 0;
  int end = n - 1;
  // [begin, end]:begin和end是左闭右闭区间,因此有=号
  while (begin <= end)
  {
    int mid = begin + ((end - begin) >> 1);
    if (a[mid] < x)
      begin = mid + 1;
    else if (a[mid] > x)
      end = mid - 1;
    else
      return mid;
  }
  return -1;
}


BinarySearch(二分查找)是一种高效的查找算法,它的时间复杂度为 O(log N),其中 N 是待查找数组的长度。


       在每一轮循环中,BinarySearch 将当前搜索范围缩小为原来的一半。假设当前搜索范围的长度为 len,在下一轮循环中,搜索范围的长度将减半为 len/2。因此,每一轮循环都可以排除一半的元素。


       最坏情况下,当搜索范围缩小到只有一个元素时,算法结束。而要将 n 个元素缩小到 1 个元素,需要进行 log₂(n) 次操作。


       因此,BinarySearch 的时间复杂度是 O(log n)。


       BinarySearch 在已排序的数组中查找元素,通过不断缩小搜索范围,每次排除掉一半的元素,因此它的时间复杂度非常低。


图解:



实例七:


// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
  if (0 == N)
    return 1;
  return Fac(N - 1) * N;
}


阶乘递归函数 Fac 的时间复杂度可以通过递归关系来分析。在这种情况下,递归的深度与输入规模 N 相关,每一层递归都会进行一次乘法操作。让我们分析一下:


第一递归层(N = N):执行 1 次 Fac(N - 1) * N乘法。

第二递归层(N = N-1):执行 1 次 Fac(N - 2) * N乘法。

第三递归层(N = N-2):执行 1 次 Fac(N - 1) * N乘法。

...

最后一层递归(N = 0):执行 1 次 Fac(0) * N乘法。

       总的乘法操作次数为 N 次。


因此,阶乘递归函数 Fac 的时间复杂度可以表示为 O(N),其中 N 是输入的规模。


       尽管递归函数的每一层都只执行了一个乘法操作,但由于递归的深度与输入规模相关,最终的时间复杂度是线性的。


       总结:递归算法时间复杂度是多次调用的累加。


扩展:


//计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{
  if (0 == N)
    return 1;
  for (size_t i = 0; i < N; ++i)
  {
    ++count;
  }
  return Fac(N - 1) * N;
}


阶乘递归函数 Fac 的时间复杂度可以通过递归关系来分析。在这种情况下,递归的深度与输入规模 N 相关,每一层递归都会进行一次乘法操作。让我们分析一下:


第一递归层(N = N):执行 1 次 Fac(N - 1) * N 乘法 + 执行 N 次 ++count。

第二递归层(N = N-1):执行 1 次 Fac(N - 2) * N 乘法 + 执行 N-1 次 ++count。

第三递归层(N = N-2):执行 1 次 Fac(N - 1) * N 乘法 + 执行 N-2 次 ++count。

...

最后一层递归(N = 0):执行 1 次 Fac(0) * N 乘法 + 执行0次 ++count。

由于上面每次递归执行的乘法只有一次,对于总的操作次数影响较小,可以忽略不记,所以总的操作次数为 N * N /2 次。


因此,阶乘递归函数 Fac 的时间复杂度可以表示为 O(N^2),其中 N 是输入的规模。


       尽管递归函数的每一层都只执行了一个乘法操作,但由于递归的深度与输入规模相关,最终的时间复杂度是线性的。


       总结:递归算法时间复杂度是多次调用的累加。


实例八:


// 计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N)
{
  if (N < 3)
    return 1;
  return Fib(N - 1) + Fib(N - 2);
}


斐波那契递归函数 Fib 的时间复杂度可以通过递归关系来分析。在这种情况下,递归的深度与输入规模 N 相关,每一层递归都会进行两次递归调用。让我们分析一下:


  1. 第一层递归(N = N):执行 2^0 次递归调用。
  2. 第二层递归(N = N-1):执行 2^2 次递归调用。
  3. 第三层递归(N = N-2):执行 2^3 次递归调用。
  4. ...

       每一层递归调用的次数是指数级别增长的, 总的乘法操作次数为 2^N-1 次。


       因此,总的递归调用次数可以近似表示为 2^N 次。


       由于每次递归调用都需要一些操作(在这里是两次递归调用),在最坏情况下,每次递归调用的时间开销相对较小。因此,总的时间复杂度仍然可以表示为 O(2^N)。


但是实际上右边会缺少,总的时间复杂度低于等于 O(2^N)。


【解密算法:时间与空间的博弈】(下):https://developer.aliyun.com/article/1424862

相关文章
|
3月前
|
存储 算法
【解密算法:时间与空间的博弈】(上)
【解密算法:时间与空间的博弈】
|
7月前
|
算法
数据结构与算法1.1关于数据结构、空间使用、算法效率、抽象数据类型
数据结构与算法1.1关于数据结构、空间使用、算法效率、抽象数据类型
45 0
|
3月前
|
存储 算法 编译器
【解密算法:时间与空间的博弈】(下)
【解密算法:时间与空间的博弈】
|
4月前
|
算法 测试技术 C#
C++前缀和算法的应用:装包裹的最小浪费空间 原理源码测试用例
C++前缀和算法的应用:装包裹的最小浪费空间 原理源码测试用例
|
6月前
|
算法
基于亚奈奎斯特采样和SOMP算法的平板脉冲响应空间插值matlab仿真
基于亚奈奎斯特采样和SOMP算法的平板脉冲响应空间插值matlab仿真
|
8月前
|
人工智能 算法
机器博弈 (三) 虚拟遗憾最小化算法
机器博弈 (三) 虚拟遗憾最小化算法
111 0
|
8月前
|
机器学习/深度学习 人工智能 开发框架
机器博弈 (二) 遗憾最小化算法
机器博弈 (二) 遗憾最小化算法
|
8月前
|
存储 算法 Java
JVM 收集算法 垃圾收集器 元空间 引用
JVM 收集算法 垃圾收集器 元空间 引用
69 0
|
9月前
|
算法 安全 Java
18-动态对象年龄判断+空间分配担保规则+老年代回收算法
本文中用到的案例是接着上一篇文章继续的,如果有不清楚同学请先查看上一篇文章
74 0
 18-动态对象年龄判断+空间分配担保规则+老年代回收算法
|
1月前
|
机器学习/深度学习 算法 生物认证
基于深度学习的人员指纹身份识别算法matlab仿真
基于深度学习的人员指纹身份识别算法matlab仿真