在那些免费网站做宣传效果好南沙区做网站

在那些免费网站做宣传效果好,南沙区做网站,成都如何做网站,网站 空间地址是什么文章目录第一章 数据结构与算法基本概念1.1 数据结构定义1.2 算法定义1.3 递归与迭代1.3.1 迭代1.3.1 递归1 递归和迭代的思想比较2 调用栈3 尾递归4 递归树5 递归和迭代对比本文记录数据结构与算法的定义#xff0c;递归和迭代的定义和比较#xff0c;下一篇笔记介绍时间复杂…文章目录第一章 数据结构与算法基本概念1.1 数据结构定义1.2 算法定义1.3 递归与迭代1.3.1 迭代1.3.1 递归1 递归和迭代的思想比较2 调用栈3 尾递归4 递归树5 递归和迭代对比本文记录数据结构与算法的定义递归和迭代的定义和比较下一篇笔记介绍时间复杂度和字符编码。第一章 数据结构与算法基本概念1.1 数据结构定义数据结构相互之间存在一种或者多种特定关系的数据元素的集合。在逻辑上可以分为线性结构、散列结构、树形结构和图形结构等。1.2 算法定义算法 求解具体问题的步骤描述代码上表现出来是解决特定问题的一组有限的指令序列。1.3 递归与迭代这一节参考了《hello 算法》的第二章。1.3.1 迭代迭代iteration是一种重复执行某个任务的控制结构。在迭代中程序会在满足一定的条件下重复执行某段代码直到这个条件不再满足。下面以for循环为例求123…100的和。intforLoop(intn){intret0;// 循环求和for(inti1;in;i){reti;}returnret;}1.3.1 递归递归recursion是一种算法策略通过函数调用自身来解决问题。它主要包含两个阶段。递程序不断深入地调用自身通常传入更小或更简化的参数直到达到“终止条件”。归触发“终止条件”后程序从最深层的递归函数开始逐层返回汇聚每一层的结果。而从实现的角度看递归代码主要包含三个要素。终止条件用于决定什么时候由“递”转“归”。递归调用对应“递”函数调用自身通常输入更小或更简化的参数。返回结果对应“归”将当前递归层级的结果返回至上一层。比如下面代码intrecursum(intn){// 1 终止条件if(n1){return1;}// 2 递归调用intretrecursum(n-1)n;coutret retendl;//3 归返回结果returnret;}理解和总结每次递归都开辟一个栈帧开始递的过程然后当n1时结束递的过程开始归归的时候从递的下面一行开始运行比如上面代码中归时每次都执行下面代码程序运行结果/* ret3ret6ret10ret15*/1 递归和迭代的思想比较以123…100为例虽然递归和迭代都能求出这个问题但是这两种完全不同的思考和解决问题的范式。迭代“自下而上”地解决问题。从最基础的步骤开始然后不断重复或累加这些步骤直到任务完成。比如先求123然后再求34…这样的方法最后求出sum() 100.从小数一直累加的方法。递归“自上而下”地解决问题。先将远问题分解为更小的问题这些子问题和原问题有相同的形式。然后再将子问题分解为更小的子问题直到基本情况时停止。比如上面的求和代码中递的过程就是分解子问题() (−1)将100分解为99100, 9899的过程一直分解为12然后开始归。2 调用栈递归函数每次调用自身时系统都会为新开启的函数分配一个栈空间。而迭代只有一个栈空间因此递归比迭代更加消费内存空间。函数调用会产生额外的开销因此递归比循环效率更低。3 尾递归如果函数在返回前的最后一步才进行递归调用则函数可以被编译器优化使其在空间上与迭代相当这中情况称为尾递归。普通递归当函数返回到上一层级的函数后需要继续执行代码因此系统需要保存上一层调用的上下文。求和操作是在“归”的过程中执行的每层返回后都要再执行一次求和操作。尾递归递归调用是函数返回前的最后一个操作这意味着函数返回到上一层级后无须继续执行其他操作因此系统无须保存上一层函数的上下文。inttailRecursum(intn,intret){// 1 终止条件if(n0){returnret;}// 2 递归调用returntailRecursum(n-1,retn);}求和操作是在“递”的过程中执行的“归”的过程只需层层返回。4 递归树当处理与“分治”相关的算法问题时递归往往比迭代的思路更加直观、代码更加易读。以“斐波那契数列”为例。Question给定一个斐波那契数列 0, 1, 1, 2, 3, 5, 8, 13, … 求该数列的第 个数字。数列的前两个数字为 (1) 0 和 (2) 1 。数列中的每个数字是前两个数字的和即 () ( − 1) ( − 2) 。代码实现intfib(intn){// 终止条件if(n1||n2){returnn-1;}// 递归调用 f(n) f(n-1) f(n-2)intretfib(n-1)fib(n-2);returnret;}上面代码在函数内递归调用了两个函数这意味着从一个调用产生了两个调用分支这样的递归会产生一个递归树层数为n的递归树以5层为例子。递归体现了“将问题分解为更小子问题”的思维范式这种分支策略至关重要。5 递归和迭代对比为了理解递归过程使用栈来模拟递归的过程intforLoopRecursum(intn){// 1 终止条件stackints;intret0;// 模拟递的过程for(intin;i0;--i){s.push(i);}// 归的过程while(!s.empty()){rets.top();s.pop();}returnret;}