02 复杂度
2023-01-05 本文已影响0人
飘摇的水草
01-开发环境搭建
-
开发工具
- Eclipse（或者IntelliJ IDEA）
- 明亮、简洁、舒服
- 多个项目可以在同一个窗口展示
- 上课过程中不会使用到后台开发的框架
- 支持Mac、Windows平台
- 下载地址：https://www.eclipse.org/downloads/
-
JDK
- 版本＞1.8
02-斐波那契数
什么是算法
- 算法是用于解决特定问题的一系列的执行步骤
- 使用不同算法，解决同一个问题，效率可能相关非常大
- 比如：求第n个斐波那契数
做这道算法题有两种做法，第一种是用递归的方式，第二种是用基本语句的方式
//方式1
int add(int n)
{
if (n <= 1) {
return n;
}
return add(n - 1) + add(n - 2);
}
//方式2
int secondAdd(int n)
{
if (n <= 1) {
return n;
}
int first = 0;
int second = 1;
int sum = 0;
for (int i = 0; i < n-1; i++)
{
sum = first + second;
first = second;
second = sum;
}
return second;
}
实际上，递归的算法虽然看起来语法简单，但实际上其花费的时间要远远大于第二种
03-算法的评估
如何评判一个算法的优劣
- 一般从以下维度来评估算法的优劣
- 正确性、可读性、健壮性（对不合理输入的反应能力和处理能力）
- 时间复杂度：估算程序指令的执行次数（执行时间）
- 空间复杂度：估算所需占用的存储空间
04-时间复杂度的估算
05-大O表示法
- 一般用大O表示法来描述复杂度，它表示的是数据规模n对应的复杂度
- 忽略常数、系数、低阶
- 9 >> O(1)
- 2n + 3 >> O(n)
- n^2 + 2n + 6 >> O(n^2)
- 4n^3 + 3n^2 + 22n + 100 >> O(n^3)
- 写法上，n^3表示n的三次方
- 注意：大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率
- 对数阶一般省略底数，所以log2 n、log9 n统称为log n
- log2 N = log2 9 * log9 n
常见复杂度比较
06-斐波那契数复杂度分析
利用递归的算法复杂度是：2^n
算法的优化方向
- 用尽量少的存储空间
- 用尽量少的执行步骤（执行时间）
- 根据情况，可以
- 空间换时间
- 时间换空间
多个变量的复杂度
