算法与算法评价算法分析与设计

算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。程序=数据结构+算法从求n个数的和出发,评价算法的好坏

#include int sum1(int n) { return (1+n)*n/2; } int sum2(int n) { int res=0; for(int i=0; i<=n; i++){ res+=i; } return res; } int main() { int n=5; printf("%d\n",sum2(n)); }

在力扣中运行代码，看执行时间哪一个比较少
输入n=3时（第一个是sum2函数，第二个是sum1）

文章图片

输入n=10000时（第一个是sum2函数，第二个是sum1）

文章图片

事后统计法
比较不同算法对同一组输入的执行处理时间
缺点：
执行时间严重依赖硬件以及运行时各种不确定的环境因素
必须编写相应的测算代码
测试数据的选择比较难保证公正性
一般从以下维度来评估算法的优劣：正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
时间复杂度（time complexity）：估算程序指令的执行次数（执行时间）大O表示法一般用大O表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度。
忽略常数、系数、低阶；对数阶一般省略底数：O(log2n) 、O(log9n) 统称为 O(logn)
两个原则
a)多项相加，保留最高阶的项。且系数变为1。
b)多项相乘，乘积之后的数再进行大O，f*g=O(f)O(g)=O(fg)。

文章图片

文章图片

时间复杂度的估算顺序执行的代码只会影响常数项，可忽略。只需要关注循环中的基本操作，分析执行次数与n的关系。
1.循环里i初始化1次，i<4的判断执行了4次，i++也是4次，输出操作也是4次

文章图片

2.

文章图片

3.第一个for循环里面的语句一共执行了n次，这取决于i；里面还有个for循环，通过上面一题知道单个for循环执行了1+3n 次。

文章图片

文章图片

4.n能除多少个2就能执行几次

文章图片

文章图片

5.第一个for循环，i要乘以几个2才能到n，就是执行次数（2的几次方是n，那么当然是log以2为底n的对数）。
for循环第二项和第三项执行次数都是相同的。
第二个for循环，很熟悉，1+3n次

文章图片

6.

文章图片

斐波那契数列的时间复杂度

public class Main { /* *0 11 2 3 5 8 13 21…… */ //第一种递归方法的时间复杂度：函数被调用了几次就执行了几次 public static int fib1(int n ) { if(n<=1) return n; return fib(n-1)+fib(n-2); } public static int fib2(int n ) { if(n<=1) return n; int first=0; int second=1; for (int i = 0; i < n-1; i++) { int sum=first+second; //两两相加，下一组的第一个数就是上一组的第二个数 //下一组的第二个数就是原来上一组的和 first=second; second=sum; } return second; } public static void main(String[] args) { System.out.print(fib2(70)); } }

分析
第一种递归方法fib1的时间复杂度：函数被调用了几次就执行了几次。
可以看到，有很多重复调用，当n=5时，先调用两次自身，再调用4次，最后调用8次。

文章图片

文章图片

所以复杂度为O(2^n)
n=6时也是一样，上下两层都是2倍关系

文章图片

而第二种非递归方法fib2的时间复杂度是O(n)
数学公式求解数列

文章图片

空间复杂度（space complexity）：估算所需占用的存储空间 【算法与算法评价】由于现在硬件发展的较好，一般情况下我们更侧重于时间复杂度。
程序在执行时，除了需要存储空间来存放本身所用的指令、常数、变量、和输入数据外，还需要一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间