- 前言
我们在前面的排序算法的学习中了解到了,排序算法的分类,效率的比较所使用到的判断标准,就包括时间复杂度和空间复杂度,当时因为这两个定义还是比较难以理解的,所以决定单独开一篇文章,记录一下学习的过程.
*** - 关于时间复杂速度与空间复杂度的基本了解
学习一项知识之前,首先要做的,就是对它要有一个基本的了解,这里我们先来看看这两者的相关的介绍:
我们通过定义简单的分析可以得出的几条简单的信息:
时间复杂度和空间复杂度都是一个函数,而函数则时用来表述两个元素之间的某一种关系的,所以时间复杂度,空间复杂度都不是指具体的某个值.
时间复杂度定性的描述算法的运行时间,说明时间复杂度是用来描述算法的运行速度的某种函数关系的,
空间复杂度是对算法需要占用的临时空间的量度,它类似于时间复杂度,也是一个函数,是关于一个问题规模为n和其消耗的内存空间的一个函数,这里我们就知道了,空间复杂度其实是类似于时间复杂度的,是相对于时间,从内存占用方面对算法的一个描述.
不管时间复杂度还是空间复杂度,都是基于一个问题规模n与时间,或内存之间的函数关系.
- 时间复杂度的理解
通过上面的简单了解,我们再深入理解其含义,明白了其实通俗来说,就是当一个算法输入的值为n的时候,算法所需要消耗的时间.
例如一个算法对于任何大小为n的输入,其运行时间为5n^3+3n,那么它的渐近时间复杂度就是O(n^3).我们知道,其实时间复杂度表示的就是渐近时间复杂度,通常都会去除函数关系中的系数和低阶项.应为当n趋近无穷大时,它们没用多大的意义,而时间复杂度所考察的就是当n趋近于无穷大时,其需要运行的时间和n的关系,所以直接就直接使用渐近时间复杂度来描述.
需要注意的时这里的n,并不是指我们所输入的指的大小,而是我们所输入数据的长度,通过前面的排序算法的学习,我们应该能够很清楚的了解到了,n就是表示需要排序的序列长度,即包含多少个需要排序的数据而不是指一个数据的大小
而在我们实际生活中,每个程序的运行时间都需要实际测算才能知道的,所以我们不可能直接通过时间来计算时间复杂度,那样不实际,那么我们通过什么来计算时间复杂度呢.我们知道一个程序的运行时间与程序的命令执行次数时相关,理论上,每条相同的执行运行的时间时相同的,所以我们在计算某个算法的时间复杂度的时候,只需要判断其操作单元(能够实现算法的基本程序指令集合)所需要执行的次数即可.
- 一些常见的时间复杂度
我们都知道,函数是描述两者这件的一种关系的,而时间复杂度就是一个函数,所以我们可以将一些常见的函数关系总结起来:
我们再来通过函数图像看看几种常见时间复杂的比较
这里可以很明显的看出各时间复杂度的优劣关系.
空间复杂度其实和时间复杂度类似,而在通常情况下,时间复杂度和空间复杂度是不能兼并的,对于递归算法,可以很简短,一般效率会比较快,但空间占用多.非递归方法通常较为复杂,不会消耗较多的空间,但其效率一般都不会很高.
参考:
更新时间:
2019-4-7
19:30