数据结构（一）

2021-11-18 本文已影响0人草帽lufei

算法描述

运算的实现是运算的算法。算法是计算机科学的一个基本概念，也是程序设计的一个核心概念。一个算法规定了求解给定问题所需要的处理步骤及其执行顺序，使得给定问题能在有限时间内被求解。

算法分析

一个问题可以有多种不同的求解算法，这就产生了如何评价这些算法的问题。通常评价算法好坏的因素包括以下几个方面：

1.正确性

能正确地实现预定的功能，满足具体问题的需要。

2.易读性

易于阅读、理解和交流，便于调试、修改和扩充。

3.健壮性

即使输入非法数据，算法也能适当地做出反应进行处理，不会产生预料不到的运行结果。

4.时空性

一个算法的时空性是指该算法的时间性能（或时间效率）和空间性能（或空间效率），前者是算法包含的计算量，后者是算法需要的存储量。

求阶乘之和

编制函数求 1！+2！+ ··· + n!

Func1

function sumFactorial (n) {
  let s = 0
  for (let i = 1; i <= n; i++) {
    let temp = 1
    for (let j = 1; j < i; j++) {
      temp += j*temp
    }
    s += temp
  }
  console.log(s)
  return s
}
sumFactorial(5)
1！+ 2！+ 3！+ 4！+ 5！
1 + 2 + 6 + 24 + 120 = 153

Func2

function sumFactorial2 (n) {
  let s = 0
  let temp = 1
  for (let i = 1; i <= n; i++) {
    temp = temp * i
    s += temp
  }
  console.log(s)
  return s
}
sumFactorial2(5)
1！+ 2！+ 3！+ 4！+ 5！
1 + 2 + 6 + 24 + 120 = 153

如何估算算法的计算量？

可在算法中合理地选择一种或几种操作作为 “基本操作” ，对给定的输入，确定算法共执行了多少次基本操作，可将基本操作次数作为该算法的时间度量。

一般情况下，一个算法的计算量是问题规模 n 的函数。当 n 充分大时， $n^2$ 这一项对 $T(n)$ 的值起着支配作用，采用数学记号 $O(n^2)$ 表示 $T(n)$ 的近似值，写为 $T(n)=O(n^2)$ ，这种表示法称为大 $O$ 表示法，它的含义是：当 n 充分大时，算法的执行时间与 $n^2$ 成正比。

大 $O$ 表示法的具体提法是：当且仅当存在正常数 $c$ 和 $n_0$ ，使得

$T(n) \leq cf(n)$

对所有 n > $n_0$ 成立。其中，f(n) 为问题规模 n 的某个函数。大 $O$ 表示法也称渐进表示法，它不考虑具体的运行时间，只给出算法在问题规模 n 下执行时间的上界。 $T(n) = O(f(n))$ 称为算法的渐进时间复杂度，简称时间复杂度。

时间复杂度常见阶数

常数阶
- 算法的时间复杂度与输入规模 n 无关
对数阶 $O(log_2n)$
线性阶 $O(n)$
多项式阶
- $O(n^2)$
- $O(n^3)$
指数阶
- C 为大于1的正整数
- $O(2^n)$

通常认为，时间复杂度具有指数阶的算法是实际不可计算的，而阶数低于平方阶的算法是高效率的。

考虑到一个算法对具有相同输入数据量的不同输入数据，时间复杂度可能会不同。通常还可以用最坏时间复杂度和平均时间复杂度来度量算法的性能。

最坏时间复杂度是指，对相同输入数据量的不同输入数据，算法时间用量最大值。

平均时间复杂度是指，对所有相同输入数据量的各种不同输入数据，算法时间用量的平均值。

空间复杂度

一个算法的空间复杂度定义为该算法所耗费的存储空间，它也是问题规模 n 的函数。通常可记为：

$S(n) = O(g(n))$

其中，g(n) 为问题规模 n 的某个函数。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量。一个算法在执行期间所需要的存储空间量应包括以下三个部分：

程序代码所占用的空间
输入数据所占用的空间
辅助变量所占用的空间

算法在执行过程中，输入数据所占用的空间是由问题决定的，它不随算法的不同而改变。程序代码所占用的空间对不同的算法来说也不会有数量级的差别。辅助变量占用的空间则有算法决定，有的需要占用随问题规模n增大而增大的临时空间，有的不随问题的规模而改变。在估算算法空间复杂度时，一般只需要分析辅助变量所占用的空间。