数据结构--算法的时间复杂度和空间复杂度

简介: 数据结构--算法的时间复杂度和空间复杂度


算法效率

算法效率是指算法在计算机上运行时所消耗的时间和资源。这是衡量算法执行速度和资源利用情况的重要指标。

例子:

long long Fib(int N)
{
  if(N < 3)
    return 1;
  return Fib(N-1) + Fib(N-2);
}

这是一个斐波那契函数,用的是递归的计算方法,每次创建函数就会在栈区开辟一块空间,递归次数越多,开辟空间越多;

所以,代码的简洁说明不了算法的效率

算法效率的评估主要包括时间复杂度和空间复杂度:

  1. 时间复杂度:时间复杂度描述了算法执行所需的时间随输入规模增加而增长的趋势。常见的时间复杂度包括常数时间O(1)、线性时间O(n)、对数时间O(log n)、平方时间O(n²)等。通过分析算法中关键操作的执行次数来确定时间复杂度,通常使用大O符号表示。
  2. 空间复杂度:空间复杂度描述了算法在执行过程中所需的额外存储空间随输入规模增加而增长的趋势。常见的空间复杂度包括常数空间O(1)、线性空间O(n)、对数空间O(log n)等。通过分析算法中使用的数据结构和辅助空间来确定空间复杂度。

评估算法效率时,我们希望选择具有更低时间复杂度和空间复杂度的算法,以提高程序的执行速度和资源利用率。但需要注意的是,时间复杂度和空间复杂度通常存在着一定的取舍关系,有时需要在时间和空间之间做出权衡。

除了时间复杂度和空间复杂度,还可以考虑一些实际情况下的算法效率问题,如最坏情况、平均情况和最好情况下的执行时间,以及算法在特定硬件环境下的性能等。综合考虑这些因素可以更全面地评估算法的效率。

为了提高算法效率,我们可以采用一些常见的优化方法,如减少循环次数、使用合适的数据结构和算法、剪枝和缓存等。同时,也可以借助工具和框架来提升算法效率,如并行计算、GPU加速、分布式计算等。

时间复杂度

时间复杂度的概念

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。

例子:计算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;
  }
  printf("%d\n", count);
}

两个循环嵌套就是N^2,再一个单独的循环2*N,加上10;

那么

F(N)=N^2+2*N+10;

N=10时,F(N)=130

N=100时,F(N)=10210

N=1000时,F(N)=1002010

会发现N越大,F(N)越接近N^2;

在实际计算时间复杂度中,我们其实不一定要精准的计算出执行的次数,只需要大概的执行次数,那么这里我们使用大O的渐进表示法;

大O的渐进表示法

大O符号(Big O notation):是用于描述函数渐进行为的数学符号。是一种用于衡量算法时间复杂度的渐进表示方法;

推导大O阶方法

1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。

用大O的渐进表示法,Func1的时间复杂度为:O(N^2)

N=10时,F(N)=100

N=100时,F(N)=10000

N=1000时,F(N)=1000000

通过计算我们发现,这样的表示方法去掉那些对结果影响不大的项,简明了洁表示出执行次数;

对于一些算法,会有好坏的情况,对于这种情况我们取最坏的情况

例如:在一个长度为N数组中搜索一个数据x

最好情况:1次找到

最坏情况:N次找到

平均情况:N/2次找到

时间复杂度O(N);

计算实例


void Func2(int N)
{
  int count = 0;
  for (int k = 0; k < 2 * N ; ++ k)
  {
    ++count;
  }
  int M = 10;
  while (M--)
  {
    ++count;
  }
  printf("%d\n", count);
}

在这里M是一个常数项,N是一个未知数,所以我们可以先把常数项略去;然后就只剩下2N,通过计算规则,省去最高项的常数;那么这个函数的时间复杂度为O(N);


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("%d\n", count);
}

在这里,M与N都是未知数,且它们是同阶的,所以对于这种情况就要分类讨论:

M与N差不多大,那么时间复杂度:O(M)或O(N)

M远大于N,时间复杂度:O(M)

N远大于M,时间复杂度:O(N)


void Func4(int N)
{
  int count = 0;
  for (int k = 0; k < 100; ++ k)
  {
    ++count;
  }
  printf("%d\n", count);
}

这里给出了明确的次数,所以时间复杂度为O(1);


const char * strchr ( const char * str, int character );

查找字符串中第一个出现的字符返回指向 C 字符串

str 中第一个出现的字符的指针。

终止空字符被视为 C 字符串的一部分。因此,也可以定位它以检索指向字符串末尾的指针。

这个就是在字符串中寻找一个字符,对于这种就要分好坏情况;

最好1次,最坏N次,时间复杂度一般看最坏,时间复杂度为 O(N)。


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次,内循环就得执行N次;那么外循环执行N次,总共就执行N^2次

时间复杂度O(N^2);


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;
}

这是一个二分查找函数,也叫折半查找;我们以最坏的情况去看,每循环一次这个数组的长度就会减半,假设以N表示数组的长度,我们要在数组中寻找一个数,那么假设寻找了x次,那么通过计算2^x=N;再通过换算就是x=log2 N;2是对数的底数,由于底数不好表示,所以对于这个函数的时间复杂度就是为O(logN);


long long Fac(size_t N)
{
if(0 == N)
return 1;
return Fac(N-1)*N;
}

这是一个阶乘递归函数,每递归一次N减1,直至为0,才返回;

那么时间复杂度为O(N)


long long Fib(size_t N)
{
if(N < 3)
return 1;
return Fib(N-1) + Fib(N-2);
}

这是开头的例子,斐波那契递归函数,每次在函数中就会递归到两个函数中去;

递归到最后,会发现像个金字塔一样,全部加起来F(N)=1+2+4+8+……+2(N-1),由数学的等比求和公式得F(N)=2^N-1;

那么时间复杂度为F(N)=2^N;

时间复杂度

空间复杂度也是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。

空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法

注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

实例


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;
  }
}

在这里函数所开辟的空间都是局部变量在栈区开辟的,是已经确定下来的;

所以,空间复杂度为O(1)


long long* Fibonacci(size_t n)
{
  if(n==0)
  return NULL;
  long long * fibArray = (long long *)malloc((n+1) * sizeof(long long));
  fibArray[0] = 0;
  fibArray[1] = 1;
  for (int i = 2; i <= n ; ++i)
  {
    fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
  }
  return fibArray;
}

这里用了malloc函数在堆区开辟了N个额外空间,所以

空间复杂度为O(N)


long long Fac(size_t N)
{
  if(N == 0)
  return 1;
  return Fac(N-1)*N;
}

这里用了递归的方法,每递归一次就会在栈帧中开辟一次空间,总共开辟N次,每次空间内为常数次大,所以

空间复杂度O(N);

常见复杂度对比

例题

这里用三种办法来解答:

第一种

时间复杂度:O(N^2)

空间复杂度:O(1)

这里利用这种方法,就是用两个循环嵌套,最终就得出了复杂度;

第二种

通过开辟额外空间,将对应位置的数字进行放入新数组中,最后再返回到原数组中;

时间复杂度:O(N)

空间复杂度:O(N)

void rotate(int* nums, int numsSize, int k){
  //开辟额外空间
  int* new=(int*)malloc(sizeof(int)*numsSize);
  //当k长度超过数组长度时
  k%=numsSize;
  memcpy(new,nums+numsSize-k,sizeof(int)*k);
  memcpy(new,nums,sizeof(int)*(numsSize-k));
  memcpy(nums,new,sizeof(int)*numsSize);
  free(new);
  
}

第三种

利用倒置再倒置的方法就将数组右旋;

时间复杂度:O(N)

空间复杂度:O(1)

//将数组进行倒置
void reserve(int* sem,int left,int right)
{
    while(left<right)
    {
        int tmp=sem[left];
        sem[left]=sem[right];
        sem[right]=tmp;
        left++;
        right--;
    }
}
void rotate(int* nums, int numsSize, int k){
    
    k%=numsSize;//如果k的长度大于numsize,需要取余
    //利用部分数组倒置,在全数组倒置的方法进行轮转
    reserve(nums,0,numsSize-k-1);
    reserve(nums,numsSize-k,numsSize-1);
    reserve(nums,0,numsSize-1);
    
}


相关文章
|
26天前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
62 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
23天前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
22天前
|
存储 算法 Java
Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性
Java Set因其“无重复”特性在集合框架中独树一帜。本文解析了Set接口及其主要实现类(如HashSet、TreeSet)如何通过特定数据结构和算法确保元素唯一性,并提供了最佳实践建议,包括选择合适的Set实现类和正确实现自定义对象的hashCode()与equals()方法。
31 4
|
24天前
|
算法
[数据结构] -- 时间复杂度和空间复杂度
[数据结构] -- 时间复杂度和空间复杂度
13 0
|
29天前
|
机器学习/深度学习 搜索推荐 算法
探索数据结构:初入算法之经典排序算法
探索数据结构:初入算法之经典排序算法
|
29天前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
17 0
|
17天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
2天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
3天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
4天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。