首页 > 编程语言 >算法与数据结构——复杂度分析

算法与数据结构——复杂度分析

时间:2024-08-19 15:53:46浏览次数:10  
标签:递归 nums int 复杂度 算法 循环 数据结构

复杂度分析

算法效率评估

在算法设计中,我们追求以下两个层面的目标。

  • 找到问题解法:算法需要再规定的输入范围内可靠地求得问题的正确解
  • 寻求最优解法:同一个问题可能存在多种解法,我们希望找到尽可能高效的算法。

也就是说,在能够解决问题的前提下,算法效率已经成为衡量算法优劣的主要评价指标,它包括以下两个度。

  • 时间效率:算法运行速度的快慢。
  • 空间效率:算法占用内存空间的大小。

复杂度分析能够体现算法运行所需要的时间和空间资源与输入数据大小之间的关系。它描述了随着输入数据的增加,算法执行所需要的时间和空间的增长趋势。

迭代与递归

在算法中,重复执行某个任务是很常见的,它与复杂度分析息息相关。因此,在介绍时间复杂度和空间复杂度之前,先了解如何在程序中实现重复执行任务,即来那个黄总基本的程序控制结构:迭代、递归

迭代

迭代(iteration)是一种重复执行某任务的控制结构。在迭代中,程序会在满足一定的条件下重复执行某代码,知道这个条件不再满足。

1.for循环

for循环是最常见的迭代形式之一,适合在预先知道迭代次数时使用

以下函数基于for循环实现了求和1+2+3+...+n,求和结果使用res记录。

int forLoop(int n){
	int res = 0;
	// 循环求和 1,2,3,4...,n
	for (int i = 1; i <= n; i++){
		res += i;
	}
	return res;
}

流程图:

此求和函数的操作与输入数据大小n成正比,或者说成“线性关系”。实际上,时间复杂度描述的就是这个“线性关系”

2.while循环

与for循环类似,while循环也是一种实现迭代的方法。在while循环中,每轮都会先检查条件,如果条件为真,则继续执行否则就结束循环。

/*while 循环*/
int whileLoop(int n){
	int res = 0;
	int i = 1;
	while (i <= n){
		res += i;
		i++;
	}
	return res;
}

while循环比for循环自由度更高。在while循环中,我们可以自由地设计条件变量的初始化和更新步骤。

3.嵌套循环

我们可以在一个循环结构内嵌套另一个循环结构,下面以for循环为例:

/* 双层 for 循环 */
string nestedForLoop(int n) {
    ostringstream res;
    // 循环 i = 1, 2, ..., n-1, n
    for (int i = 1; i <= n; ++i) {
        // 循环 j = 1, 2, ..., n-1, n
        for (int j = 1; j <= n; ++j) {
            res << "(" << i << ", " << j << "), ";
        }
    }
    return res.str();
}

嵌套循环流程框图:

 在这种情况下,函数的操作数量与n2成正比,或者说算法运行时间和输入数据大小n成“平方关系”。我们可以继续添加嵌套循环,每一次嵌套都是一次“升维”,将会使其时间复杂度提高至“立方关系”“四次关系”,以此类推。

递归

递归(recursion)是一种算法策略,通过函数调用自身来解决问题。它主要包含两个阶段。

  • 递:程序不断深入地调用自身,通常传入更小或更简化的参数,知道达到“终止条件”。
  • 归:触发“终止条件”后,程序从最深层的递归函数开始逐层返回,汇聚每一层的结果。

而从实现的角度看,递归代码主要包含三个要素。

  • 终止条件:用于决定什么时候由“递”转为“归”。
  • 递归调用:对应“递”,函数调用自身,通常输入更小后更简化的参数。
  • 返回结果:对应“归”,将当前递归层级的结果返回至上一层。

观察以下代码,我们只需要调用函数recur(n)就可以完成1+2+3+...+n的计算

/*递归调用*/
int recur(int n){
	if (n == 1){
		return 1;
	}
	return n + recur(n - 1);
}

递归过程:

 

虽然从计算角度看,迭代与递归可以得到相同的结果,但他们代表了两种完全不同的思考和解决问题的范式。

  • 迭代:“自下而上”地解决问题。从最基础的步骤开始,然后不断重复或累加这些步骤,直到任务完成。
  • 递归:“自上而下”地解决问题。将原问题分解为更小的子问题,这些子问题和原问题具有相同的形式。接下来将子问题继续分解为更小的子问题,直到基本情况时停止(基本情况的解是已知的) 

上述求和函数为例,设问题

标签:递归,nums,int,复杂度,算法,循环,数据结构
From: https://www.cnblogs.com/1873cy/p/18366749

相关文章

  • Java中的可达性分析算法图解,以及哪些对象可以作为GCRoots
    可达性分析算法图示:解释:因为在GCRoots中存在对于对象A的引用,而A又持有对对象B和对象C的引用,所以这一串都是有用的引用链,需要保留。对于对象D和对象E,他们只是相互进行引用,并没有和GCRoots中的对象有任何的关联,所以可以安全的回收。哪些对象可以作为GCRoots虚拟机栈(栈帧中的......
  • 【杂乱笔记】Kmp字符串匹配算法
    KMP算法逻辑构建next数组:初始化next数组,用于存储每个位置的最长相同前后缀长度。遍历模式字符串patt如果当前字符与前缀字符匹配,增加前缀长度,并更新next数组。如果不匹配,使用next[prefix\_len-1]回退到上一个可能的前缀长度,继续比较。字符串匹配:初始......
  • 实现strStr() —— KMP算法(包含next数组的优化)
    目录KMP算法KMP算法的应用前缀表最长公共前后缀为什么要使用前缀表如何计算前缀表前缀表和next数组时间复杂度分析例题28.实现strStr构造next数组 使用next数组来做匹配 前缀表统一减一C++代码实现前缀表(不减一)C++代码实现总结 拓展:next数组的优化 KMP算......
  • 常见的排序算法汇总(详解篇)
    目录排序的概念以及运用排序的概念1.插入排序1.1直接插入排序1.1.1 基本思想1.1.2代码实现直接插入排序的特征总结:1.1.3希尔排序(缩小增量排序)......
  • 数据结构(二)- 线性表
    数据结构(二)-线性表数据结构三要素——逻辑结构、数据的运算、存储结构;存储结构不同运算实现的方式不同;1.线性表的定义定义:线性表是具有相同数据类型的n(n>0)个数据元素的有限序列,其中n为表长,当n=0线性表是一个空表。一般表示为L=(a1,a2,…,ai,ai+1,…,an)......
  • 迪杰斯特拉(Dijkstra)算法(C/C++)
    迪杰斯特拉(Dijkstra)算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。它是由荷兰计算机科学家艾兹格·迪科斯彻(EdsgerDijkstra)在1956年提出的。Dijkstra算法适用于处理带有非负权重的图。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法,每次遍历到始......
  • 2024年新SCI顶刊算法蛇鹭优化算法SBOA优化Transformer-LSTM模型的多变量时间序列预测
    matlabR2024a以上一、数据集二、2024年新SCI顶刊算法蛇鹭优化算法SBOA2024年,YFu受到自然界中鹭鹰生存行为启发,提出了鹭鹰优化算法(SecretaryBirdOptimizationAlgorithm,SBOA)。2.1算法思想SBOA生存需要不断地寻找猎物和躲避捕食者的追捕,探索阶段模拟鹭鹰捕食蛇,而......
  • Manacher 算法
    算法介绍\(\text{Manacher}\)算法(又名马拉车),是一种常用于处理回文字符串的算法。其代码量很小,却可以在\(O(n)\)的时间复杂度内处理问题算法思想和其他大多数算法一样,\(\text{Manacher}\)算法利用现有的信息获得下一部分的信息。经典例题:给定一个字符串\(s\)。求出其最长......
  • ACM算法——数学专题
    一、素数1、欧拉筛时间复杂度:\(O(n)\)constexprintN=1E6;std::vector<int>primes;std::vector<bool>st;voidinit(intn){st.assign(n+1,false);primes.clear();for(inti=2;i<=n;i++){if(!st[i]){pri......
  • 经典分治算法
    RT,主要介绍一些经典的分治算法CDQ分治经典人类智慧算法。三维偏序问题三维偏序是CDQ分治的一个经典应用,搭配树状数组可以在\(O(n\log^2n)\)的时间复杂度内解决问题。如果我们枚举每一个元素,然后枚举其他的元素的话,可以在\(O(n^2)\)的时间复杂度解决这个问题,但显然无法......