目录
1、算法复杂度
1.1 概念
算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。
1.2 评价指标
如何去衡量不同算法之间的优劣?
从算法所占用的「时间」和「空间」两个维度去考量。
- 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
- 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。
因此,评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而,有的时候时间和空间却又是「鱼和熊掌」,不可兼得的,那么我们就需要从中去取一个平衡点。
下面我来分别介绍一下「时间复杂度」和「空间复杂度」的计算方式。
1.3 时间复杂度
1.3.1 什么是时间复杂度
我们想要知道一个算法的「时间复杂度」,很多人首先想到的的方法就是把这个算法程序运行一遍,那么它所消耗的时间就自然而然知道了。
这种方式可以吗?当然可以,不过它也有很多弊端。
这种方式非常容易受运行环境的影响,在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。而且对测试时使用的数据规模也有很大关系。当然,还需考虑算法还没有办法完整的去运行的情况。
因此,另一种更为通用的方法就出来了:「 大O(符号)表示法 」,即 T(n) = O(f(n))
我们先来看个例子:
for i in range(n): # 行1
j = i # 行2
j++; # 行3
通过「 大O(符号)表示法 」,这段代码的时间复杂度为:$O(n)$ ,为什么呢?
在 大O表示法中,时间复杂度的公式是: T(n) = O( f(n) ),其中f(n) 表示每行代码执行次数之和,而 O 表示正比例关系,这个公式的全称是:渐进时间复杂度(asymptotic complexity)。
我们继续看上面的例子,假设每行代码的执行时间都是一样的,我
标签:1.4,1.3,复杂度,算法,时间,空间,数据结构 From: https://blog.csdn.net/weixin_45736855/article/details/143227967