目录:
一.算法定义
二.空间复杂度
三.时间复杂度
四.总结
一.算法定义
算法(Algorithm)是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,
算法代表着用系统的方法描述解决问题的策略机制。也就是说,能够对一定规范的输入,在有限时间内获得所要求的输出。
如果一个算法有缺陷,或不适合于某个问题,执行这个算法将不会解决这个问题。
不同的算法可能用不同的时间、空间或效率来完成同样的任务。
一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
二.空间复杂度
空间复杂度是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。
三.时间复杂度
时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
算法的效率 : 算法所处理的数据个数n 的函数。
关键代码的执行次数
O(n) 表示
当n无穷大时,
O(n) = n^2 + 3n + 100 == > O(n) = n^2
O(n) = n^4 + n^5 + n => On = n^5
示例:
public void function1() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// dosomething;
}
}
for (int i = 0; i < n; i++) {
//dosomething
}
// dosomething
}
时间复杂度 O(n) = n^2 + n + 1 => On = n^2
public void function2() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
// dosomething;
}
}
}
时间复杂度 O(n) = n^2 => On = n^2
function1和function2 时间复杂度相等
四.总结
程序好坏=空间复杂度+时间复杂度+应用场景(重要)