Hello-算法笔记
算法效率评估算法algorithm是在有限时间内解决特定问题的一组指令或操作步骤
数据结构 data structure是计算机中组织和存储数据的方式
数据结构与算法高度相关、紧密结合，具体表现以下三个方面：
[*]数据结构是算法的基石
数据结构为算法提供了结构化存储的数据，以及用于操作数据的方法
[*]算法是数据结构发挥作用的舞台
数据结构本身仅存储数据信息，结合算法才能解决特定问题
[*]算法通常可以基于不同的数据结构进行实现
但执行效率可能相差很大，选择合适的数据结构是关键
在算法设计中，先后追求以下两个层面的目标
[*]找到问题解法：算法需要在规定的输入范围内，可靠地求得问题的正确解
[*]寻求最优解法：同一个问题可能存在多种解法，找到尽可能高效的算法
也就是说，在能够解决问题的前提下，算法效率已成为衡量算法优劣的主要评价指标，它包括以下两个维度
[*]时间效率：算法运行速度的快慢
[*]空间效率：算法占用内存空间的大小
渐近复杂度分析(asymptotic complexity analysis)，简称「复杂度分析」
复杂度分析体现算法运行所需的时间（空间）资源与输入数据大小之间的关系。它描述了随着输入数据大小的增加，算法执行所需时间和空间的增长趋势
[*]时间和空间资源分别对应时间复杂time complexity和空间复杂度 space complexity
[*]随着输入数据大小的增加意味着复杂度反映了算法运行效率与输入数据体量之间的关系
[*]时间和空间的增长趋势表示复杂度分析关注的不是运行时间或占用空间的具体值，而是时间或空间增长的快慢
如果函数在返回前的最后一步才进行递归调用，则该函数可以被编译器或解释器优化，使其在空间效率上与迭代相当。这种情况被称为尾递归tail recursion
/* 尾递归 */
int TailRecur(int n, int res) {
// 终止条件
if (n == 0)
return res;
// 尾递归调用
return TailRecur(n - 1, res + n);
}但许多编译器或解释器不支持尾递归优化
当处理与分治相关的算法问题时，递归往往比迭代的思路更加直观、代码更加易读。以“斐波那契数列”为例:
/* 斐波那契数列：递归 */
int Fib(int n) {
// 终止条件 f(1) = 0, f(2) = 1
if (n == 1 || n == 2)
return n - 1;
// 递归调用 f(n) = f(n-1) + f(n-2)
int res = Fib(n - 1) + Fib(n - 2);
// 返回结果 f(n)
return res;
}迭代递归实现方式循环结构函数调用自身时间效率效率通常较高。无函数调用开销每次函数调用都会产生开销内存使用通常使用固定大小的内存空间累积函数调用可能使用大量的栈帧空间适用问题适用于简单循环任务，代码直观、可读性好可适用于子问题分解。如树、图、分治、回溯等，代码结构读性好、简洁、清晰时间复杂度
***时间复杂度指算法运行时间随着数据量变大时的增长趋势
title:计算时间复杂度操作数量
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]