算法-从入门到放弃-1

什么是算法

​ 算法，指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。算法有其自己的特性，其中包含有穷性、确切性、输入项、输出项、可行性这些特征。

​ 算法代表着用系统的方法描述解决问题的策略机制。算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。

简单而言，就是找出一类问题的解的方法。有了合适的算法，我们可以大幅提高程序的运行效率，在减少资源占用的前提下，得令人满意的处理结果。

算法复杂度

时间复杂度

对于时间复杂度，光听名字，我们猜测它和算法运行的时间密切相关。

在此，我们给出时间复杂度的精确定义

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。这是一个关于代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。

简单而言，时间复杂度就是执行算法所需要的计算工作量

时间复杂度的计算方法

一般情况下，算法重复执行的次数是模块n的一个函数f(n)，因此，算法的时间复杂度记作T(n)=O(f(n))。在实践中，我们先找出算法的基本操作，然后根据相应的各语句确定它的执行次数

《数据结构(C语言版)》------严蔚敏 吴伟民编著 第15页有句话"整个算法的执行时间与基本操作重复执行的次数成正比。"

举例分析

我们拿求Fibocnacci的第n项数的两种方法为例

  • 递归法

    def factorial_recursive(n):
  if n == 0 or n == 1:
      return 1
  else:
      return n * factorial_recursive(n - 1)

    对于每一项n，函数被分解为两个更小的子问题：n-1和n-2。

    每个子问题又继续分解，导致调用次数以指数级增长。

    时间复杂度可以用递推公式 T(n) = T(n-1) + T(n-2) + O(1) 表示，其中O(1)是除递归调用外的运算复杂度。

    这个公式的解接近于黄金分割比的指数，即Φ^n，其中Φ是黄金分割比（约等于1.618）。

    因此，递归法的时间复杂度是O(Φ^n)，也可近似为O(2^n)。

  • 迭代法

    def fibonacci_iterative(n):
  if n <= 1:
      return n
  a, b = 0, 1
  for _ in range(2, n + 1):
      a, b = b, a + b
  return b

    在迭代法中，我们使用两个变量a和b来迭代计算Fibonacci数列。

    每次迭代只涉及常数级别的操作。

    因此，对于计算第n项，需要进行n-1次迭代。

    时间复杂度是O(n)

空间复杂度

我们在空间复杂度的定义上使用类比推理法，可以猜测空间复杂度的定义，这里我们不多赘述，直接给出定义

空间复杂度是用来描述算法在运行过程中在内存中所占用空间大小的一个量化标准。它不仅考虑了算法中使用的数据存储量，也包括了算法的执行过程中栈、队列等数据结构所占用的空间。

空间复杂度的计算

固定部分：这是算法执行所需的固定空间，包括存储算法输入输出的空间、算法内部使用的变量和常量的存储空间等。例如，对于简单的算术运算，这个空间是常数。

可变部分：这部分是随着输入数据的规模变化而变化的空间。例如，如果算法需要一个与输入数据大小成比例的数组，那么这部分空间就是和输入规模线性相关的。

递归栈空间：在递归算法中，每一次递归调用都会在栈上创建一个新的局部变量和参数的副本。递归的深度会直接影响到所需的栈空间大小。

总体上，空间复杂度的计算公式可以表示为：S(n) = C + f(n)，其中：

S(n) 是总空间复杂度，
C 是固定空间部分，
f(n) 是随输入规模n变化的空间部分。
例如，对于非递归算法，如果只使用了固定数量的变量，则其空间复杂度是 O(1)；如果使用了大小与输入数据规模成比例的数组，则空间复杂度是 O(n)。

在算法分析中，空间复杂度通常是次要考虑的因素，主要集中于时间复杂度。但在空间资源受限的情况下（例如很多算法竞赛对内存占用有着很高程度的要求），空间复杂度也是一个重要的考量指标。

​