复杂性的计量 两种求斐波那契数列前+1项算法的效率比较 void Fibonacci(int n){∥假定n>=0,递归算法 int i; for (i=0;i<=n;i++)printf("%d n",fib(n)); int fib(intk）{ if (k =0)return 0; else if (k =1)return 1; else return fib(k -1)fib(k 2); 对该数列ao,a1,,an,ax(0≤k<n)被重复计算多次
复杂性的计量 • 两种求斐波那契数列前n+1项算法的效率比较 void Fibonacci(int n) { // 假定n >= 0，递归算法 int i; for (i = 0; i <= n; i++) printf(“%d\n”, fib(n)); } int fib(int k) { if (k == 0) return 0; else if (k == 1) return 1; else return fib(k −1) + fib(k − 2); } 对该数列a0 , a1 , …, an , ak (0 k < n)被重复计算多次 12
复杂性的计量 两种求斐波那契数列前+1项算法的效率比较 void Fibonacci(int n){∥假定n>=0,循环算法 int j0,j1,i,temp; j0=0;j1=1; for(i=0;i<=n;i++){ printf(%dn”,j0); temp j1;j1 j0 +j1;j0 temp; 4(0≤k≤n)都只计算1次，显然效率高于前一个算法
复杂性的计量 • 两种求斐波那契数列前n+1项算法的效率比较 void Fibonacci(int n) { // 假定n >= 0，循环算法 int j0, j1, i, temp; j0 = 0; j1 = 1; for(i = 0; i <= n; i ++) { printf(“%d\n”, j0); temp = j1; j1 = j0 + j1; j0 = temp; } } ak (0 k n)都只计算1次, 显然效率高于前一个算法 13
复杂性的计量 两种求斐波那契数列前+1项算法的效率比较 void Fibonacci(int n){∥假定n>=0,循环算法 int j0,j1,i,temp; j0=0;j1=1; for(i=0;i<=n;i++){ printf(%dn”,j0); temp j1;j1 j0 +j1;j0 temp; 这种比较单纯反映作为算法精髓的计算方法本身 的效率，不涉及运行这些算法的实际计算机的性能 1
复杂性的计量 • 两种求斐波那契数列前n+1项算法的效率比较 void Fibonacci(int n) { // 假定n >= 0，循环算法 int j0, j1, i, temp; j0 = 0; j1 = 1; for(i = 0; i <= n; i ++) { printf(“%d\n”, j0); temp = j1; j1 = j0 + j1; j0 = temp; } } 这种比较单纯反映作为算法精髓的计算方法本身 的效率，不涉及运行这些算法的实际计算机的性能 14
复杂性的计量 ,复杂性函数 -时间和空间复杂性函数分别是：TN,D和SN,D N:问题规模，I:算法的输入 问题 问题的规模N 在数组中查找值为a的分量 数组中分量个数 矩阵相乘 矩阵的阶 数表的排序 数表中的项数 遍历二叉树 树中节点数 求数列的前n项 项数n 解有关图的问题 图中节点数或边数
复杂性的计量 • 复杂性函数 – 时间和空间复杂性函数分别是：T(N, I)和S(N, I) N：问题规模， I：算法的输入 问题 问题的规模N 在数组中查找值为val的分量 数组中分量个数 矩阵相乘 矩阵的阶 数表的排序 数表中的项数 遍历二叉树 树中节点数 求数列的前n项 项数n 解有关图的问题 图中节点数或边数15