Java教程

评价算法的复杂度

本文主要是介绍评价算法的复杂度,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

评估算法优劣的核心指标?

时间复杂度:(流程决定)

首先看一个概念:

常数时间的操作:如果一个操作的执行时间不以具体样本量为转移,每次执行时间都是固定时间。称这样的操作作为常数时间的操作。(说白了就是和数据量无关的,数据量变化每次执行时间都固定下来的常数时间操作,)

常见的常数时间操作:

常见的算术运算(+、-、*、/、%等)
常见的位运算(>>、>>>、<<、|、&、^等)赋值、比较、自增、自减操作等
数组寻址操作

时间复杂度就是发生了多少次的常数操作,

如何确定算法流程的总操作数量与样本数量之间的表达式关系?

1,想象该算法流程所处理的数据状况,要按照最差情况来。
2,把整个流程彻底拆分为一个个基本动作,保证每个动作都是常数时间的操作。
3,如果数据量为N,看看基本动作的数量和N是什么关系。

当完成了表达式的建立,只要把最高阶项留下即可。低阶项都去掉,高阶项的系数也去掉。
记为: o(忽略掉系数的高阶项)

时间复杂度的意义

抹掉了好多东西,只剩下了一个最高阶项啊…那这个东西有什么意义呢?
时间复杂度的意义在于:
当我们要处理的样本量很大很大时,我们会发现低阶项是什么不是最重要的;每一项的系数是什么,不是最重要的。真正重要的就是最高阶项是什么。
这就是时间复杂度的意义,它是衡量算法流程的复杂程度的一种指标,该指标只与数据量有关,与过程之外的优化无关。

额外空间复杂度:(流程决定)

你要实现一个算法流程,在实现算法流程的过程中,你需要开辟一些空间来支持你的算法流程。

作为输入参数的空间,不算额外空间。

作为输出结果的空间,也不算额外空间。

因为这些都是必要的、和现实目标有关的。所以都不算。

但除此之外,你的流程如果还需要开辟空间才能让你的流程继续下去。这部分空间就是额外空间。如果你的流程只需要开辟有限几个变量,额外空间复杂度就是O(1)。

与功能无关,自己开辟的额外空间。

常数项时间:(实现细节决定)

算法流程是一样的话,就需要关心常数项,

我们会发现,时间复杂度这个指标,是忽略低阶项和所有常数系数的。难道同样时间复杂度的流程,在实际运行时候就一样的好吗?
当然不是。
时间复杂度只是一个很重要的指标而已。如果两个时间复杂度一样的算法,你还要去在时间上拼优劣,就进入到拼常数时间的阶段,简称拼常数项。

常见的时间复杂度:

排名从好到差:

O(1)

O(logN)

O(N)

O(N*logN)

O(N^2) O(N个3).......O(N^K)

O(2^N) O(3^N).......... O(K^N)

O(N!)

这篇关于评价算法的复杂度的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!