算法的基础知识
算法的定义
算法是为了解决某类问题而规定的一个有限长的操作序列。
算法的特性
1. 有穷性（Finiteness）
- 含义：一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
- 重要性：确保算法能够在合理的时间内完成，不会陷入无限循环。
2. 确定性（Definiteness）
- 含义：对于每种情况下所应执行的操作，在算法中都有确切的规定，不会产生二义性，算法的执行者或阅读者都能明确其含义及如何执行。
- 重要性：确保算法的每一步都可以被精确执行，不同的人执行同一算法会得到相同的结果。
3. 可行性（Effectiveness）
- 含义：算法中的所有操作都可以通过将已经实现的基本操作运算执行有限次来实现。
- 重要性：确保算法不仅是理论上的，而且是实际可执行的，可以通过现有的技术手段实现。
4. 输入（Input）
- 含义：一个算法有0个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。
- 重要性：输入是算法处理的基础，没有输入，算法无法开始执行。在函数形式中，输入通常通过参数传递。
5. 输出（Output）
- 含义：一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。
- 重要性：输出是算法执行的目的。
评价算法优劣的基本标准
应该从以下几方面来评价
1.正确性:
在合理的数据输入下，好的算法能够在有限的运行时间内得到正确的结果。
2.可读性:
一个好的算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法容易隐藏错误，且难于调试和修改。
3.健壮性:
当输入的数据非法时，好的法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。
4.高效性:
高效性包括时间和空间两个方面。时间高效是指算法设计合理，执行效率高，可以用时间复杂度来度量；空间高效是指算法占用存储容量合理，可以用空间复杂度来度量。时间复杂度和空间复杂度是衡量算法的两个主要指标。
算法时间复杂度
1. 时间复杂度的重要性
算法的时间复杂度是衡量算法执行时间随输入规模增长的变化趋势。它帮助我们评估算法的效率，并在多个算法中选择最优解。
2. 时间复杂度的基本概念
- 问题规模：用整数n表示，不同问题中n的含义不同。
- 语句频度：一条语句的重复执行次数，直接影响算法的执行时间。
设每条语句执行一次所需的时间均是单位时间，则一个算法的执行时间可用该算法中所有语句频度之和来度量。
3. 时间复杂度的定义
- 基本语句：算法中重复执行次数和算法的执行时间成正比的语句，它对算法运行时间的贡献最大。
- 渐近时间复杂度：一般情况下，算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作： T(n) = O(f(n))
它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度（Time Complexity）。
4. 时间复杂度的数学定义
- O符号：表示数量级:
5. 时间复杂度的分析方法
- 找出基本语句：确定算法中执行次数最多的语句。
- 计算频度：计算基本语句的频度，得到问题规模n的函数f(n)。
- 确定数量级：用O符号表示f(n)的数量级。
6. 时间复杂度的常见类型
- 常量阶：O(1)
- 对数阶：O(log n)
- 线性阶：O(n)
- 平方阶：O(n^2)
- 立方阶：O(n^3)
- k次方阶：O(n^k)
- 指数阶：O(2^n)
常量阶示例
{x++; s=0;}
- 频度：两条语句的频度都是1。
- 时间复杂度：T(n) = O(1)，与输入规模n无关。
线性阶示例
for(i=0; i<n; i++) { x++; s=0; }
- 频度：循环执行n次。
- 时间复杂度：T(n) = O(n)，与输入规模n线性相关。
立方阶示例
for(k=1; k<=n; k++)
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
y++;
- 频度：最内层循环的频度为n^3。
- 时间复杂度：T(n) = O(n^3)，与输入规模n的立方相关。
for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
for(k=1; k<=j; k++)
x++;
- 频度：总频度大约为n^3/6。
- 时间复杂度：T(n) = O(n^3)，与输入规模n的立方相关。
对数阶示例
for(i=1; i<=n; i=i*2)
x++;
- 频度：需要log2(n)次循环。
- 时间复杂度：T(n) = O(log2n)，与输入规模n的对数相关。
7. 最好、最坏和平均时间复杂度
- 最好时间复杂度：算法在最好情况下的时间复杂度，是指算法计算量可能达到的最小值；
- 最坏时间复杂度：算法在最坏情况下的时间复杂度，是指算法计算量可能达到的最大值；
- 平均时间复杂度：算法在所有可能情况下，按照输入实例以等概率出现时，算法计算量的加权平均值。
- 通常只讨论算法在最坏情况下的时间复杂度，即分析在最坏情况下，算法执行时间的上界。
最好、最坏和平均时间复杂度示例
for(i=0; i<n; i++)
if(a[i] == e) return i+1;
return 0;
- 最好情况：如果e是第一个元素，频度为1。
- 最好时间复杂度：T(n) = O(1)
- 最坏情况：如果e是最后一个元素或不存在，频度为n。
- 最坏时间复杂度：T(n) = O(n)
- 平均情况：假设e在数组中任意位置出现的概率相等，平均频度为n/2。
- 平均时间复杂度：T(n) = O(n)
算法空间复杂度
算法的空间复杂度是衡量算法在执行过程中所需的存储空间的量度，类似于时间复杂度，它也是问题规模n的函数，记作S(n) = O(f(n))。
1. 空间复杂度的定义
- 渐近空间复杂度：算法所需存储空间的量度，是问题规模n的函数。
- 辅助空间：除了输入数据本身，算法执行时还需要一些对数据进行操作的辅助存储空间。
2. 空间复杂度的分类
- 原地工作：如果算法执行时所需要的辅助空间相对于输入数据量而言是个常数，则称这个算法在原地工作，辅助空间为O(1)。
- 非原地工作：如果算法需要占用的临时工作单元数与问题规模n有关，则空间复杂度为O(n)或其他。
例：数组逆序
-
算法1：
for(i=0; i<n/2; i++) { t = a[i]; a[i] = a[n-i-1]; a[n-i-1] = t; }- 分析：算法1仅需要一个额外的变量t来交换元素，与问题规模n大小无关。
- 空间复杂度：S(n) = O(1)。
-
算法2：
for(i=0; i<n; i++) b[i] = a[n-i-1]; for(i=0; i<n; i++) a[i] = b[i];- 分析：算法2需要一个大小为n的辅助数组b来存储逆序后的元素。
- 空间复杂度：S(n) = O(n)。
时间复杂度与空间复杂度的关系
- 相互影响：追求较好的时间复杂度可能会导致占用较多的存储空间，反之亦然。
- 权衡：在实际应用中，通常更关注算法的时间复杂度，因为运算空间相对充足。
原文地址：https://blog.csdn.net/Xiao_die888/article/details/143578130
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！