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