数据结构之数据结构、时间复杂度、空间复杂度

文章目录

• 数据结构之数据结构、时间复杂度、空间复杂度
• • 1.数据结构分类
  • • 1.1逻辑结构
    • 1.2物理结构
  • 2.时间复杂度介绍
  • 3.大O
  • 4.不同数据规模的差异
  • 5.时间复杂度化简
  • 6.分析O(logn)中的log底数
  • 7.超时解决办法
  • 8.只在乎核心代码
  • 9.找出相同字符串求时间复杂度
  • 10.迭代求时间复杂度
  • 11.调用函数求时间复杂度
  • 12.复杂情况求时间复杂度
  • 13.空间复杂度
  • 14.空间复杂度是O(1)
  • 15.空间复杂度是O(n)
  • 16.代码的内存消耗

数据结构之数据结构、时间复杂度、空间复杂度 1.数据结构分类 1.1逻辑结构

1.2物理结构

2.时间复杂度介绍

时间复杂度是一个函数，它定性描述该算法的运行时间。

我们在软件开发中，时间复杂度就是用来方便开发者估算出程序运行的答题时间。

那么该如何估计程序运行时间呢，通常会估算算法的 *** 作单元数量来代表程序消耗的时间，这里默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为n，那么 *** 作单元数量便用函数f(n)来表示，随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为O(f(n)。

3.大O

这里的大O是指什么呢，说到时间复杂度，大家都知道O(n)，O(n^2)，却说不清什么是大O。

算法导论给出的解释：大O用来表示上界的，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

同样算法导论给出了例子：拿插入排序来说，插入排序的时间复杂度我们都说是O(n^2) 。

输入数据的形式对程序运算时间是有很大影响的，插入排序在数据本来有序的情况下时间复杂度是O(n)，但如果数据是逆序的话，插入排序的时间复杂度就是O(n^2)，也就对于所有输入情况来说，最坏是O(n^2) 的时间复杂度，所以称插入排序的时间复杂度为O(n^2)。

同样的同理再看一下快速排序，都知道快速排序是O(n*log n)，但是当数据最坏情况下，快速排序的时间复杂度是O(n^2)的，所以严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)。

但是我们依然说快速排序是O(n*log n)的时间复杂度，这个就是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界。

我们主要关心的还是一般情况下的数据形式。

面试中说道算法的时间复杂度是多少指的都是一般情况。

但是如果面试官和我们深入探讨一个算法的实现以及性能的时候，就要时刻想着数据用例的不一样，时间复杂度也是不同的，这一点是一定要注意的。

4.不同数据规模的差异

在决定使用哪些算法的时候，不是时间复杂越低的越好（因为简化后的时间复杂度忽略了常数项系数等等），要考虑数据规模，如果数据规模很小甚至可以用O(n^2)的算法比O(n)的更合适（在有常数项系数的时候）。

就像下图中 O(5n^2) 和 O(100n) 在n为20之前 很明显 O(5n^2)是更优的，所花费的时间也是最少的。

那为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说O(100n) 就是O(n)的时间复杂度，O(5n^2) 就是O(n^2)的时间复杂度，而且要默认O(n)优于O(n^2)呢 ？
这里就又涉及到大O的定义，因为大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量。

例如上图中20就是那个点，n只要大于20 常数项系数已经不起决定性作用了。

所以我们说的时间复杂度都是省略常数项系数的，是因为一般情况下都是默认数据规模足够的大，基于这样的事实，给出的算法时间复杂的的一个排行如下所示：
O(1)常数阶 < O(log n)对数阶 < O(n)线性阶 但是也要注意大常数项系数，如果这个常数非常大，例如10^7 ，10^9 ，那么常数就是不得不考虑的因素了

5.时间复杂度化简

O(2*n^2 + 10n + 1000):
1.因为常数项并不会因为n的增大而增加计算机的 *** 作数,所以去掉运行时间中的加法常数项:O(2*n^2 + 10n)
2.去掉常数系数（上文中已经详细讲过为什么可以去掉常数项的原因）:
O(n^2 + n)
3.只保留保留最高项，去掉数量级小一级的n （因为n^2 的数据规模远大于n），最终简化为：
O(n^2)
所以最后我们说：这个算法的算法时间复杂度是O(n^2) 。

6.分析O(logn)中的log底数

平时说这个算法的时间复杂度是logn的，那么一定是log 以2为底n的对数么？
其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，但我们统一说 logn，也就是忽略底数的描述。

为什么可以这么做呢？如下图所示：

假如有两个算法的时间复杂度，分别是log以2为底n的对数和log以10为底n的对数，那么这里如果还记得高中数学的话，应该不难理解以2为底n的对数 = 以2为底10的对数 * 以10为底n的对数。

而以2为底10的对数是一个常数，在上文已经讲述了我们计算时间复杂度是忽略常数项系数的。

抽象一下就是在时间复杂度的计算过程中，log以i为底n的对数等于log 以j为底n的对数，所以忽略了i，直接说是logn。

这样就应该不难理解为什么忽略底数了

7.超时解决办法

大家在leetcode上练习算法的时候应该都遇到过一种错误是“超时”。

也就是说程序运行的时间超过了规定的时间，一般OJ（online judge）的超时时间就是1s，也就是用例数据输入后最多要1s内得到结果，但暂时还不清楚leetcode的判题规则
如果n的规模已经足够让 O ( n ) O(n) O(n)的算法运行时间超过了1s，就应该考虑log(n)的解法了。

8.只在乎核心代码

9.找出相同字符串求时间复杂度

通过这道面试题目，来分析一下时间复杂度。

题目描述：找出n个字符串中相同的两个字符串（假设这里只有两个相同的字符串）。

如果是暴力枚举的话，时间复杂度是多少呢，是O(n^2)么？
这里一些同学会忽略了字符串比较的时间消耗，这里并不像int 型数字做比较那么简单，除了n^2 次的遍历次数外，字符串比较依然要消耗m次 *** 作（m也就是字母串的长度），所以时间复杂度是O(m × n × n)。

接下来再想一下其他解题思路。

先排对n个字符串按字典序来排序，排序后n个字符串就是有序的，意味着两个相同的字符串就是挨在一起，然后在遍历一遍n个字符串，这样就找到两个相同的字符串了。

那看看这种算法的时间复杂度，快速排序时间复杂度为O(nlog n)，依然要考虑字符串的长度是m，那么快速排序每次的比较都要有m次的字符比较的 *** 作，就是O(m × n × log n)
之后还要遍历一遍这n个字符串找出两个相同的字符串，别忘了遍历的时候依然要比较字符串，所以总共的时间复杂度是 O(m × n × log n + n × m)。

我们对O(m × n × log n + n × m) 进行简化 *** 作，把m × n提取出来变成 O(m × n × (log n + 1))，再省略常数项最后的时间复杂度是 O(m × n × log n)。

最后很明显O(m × n × log n) 要优于O(m × n × n)！
所以先把字符串集合排序再遍历一遍找到两个相同字符串的方法要比直接暴力枚举的方式更快。

这就是我们通过分析两种算法的时间复杂度得来的。

当然这不是这道题目的最优解，我仅仅是用这道题目来讲解一下时间复杂度

10.迭代求时间复杂度

11.调用函数求时间复杂度

12.复杂情况求时间复杂度

13.空间复杂度

什么是空间复杂度呢？
是对一个算法在运行过程中占用内存空间大小的量度，记做S(n)=O(f(n)$。

空间复杂度(Space Complexity)记作S(n) 依然使用大O来表示。

利用程序的空间复杂度，可以对程序运行中需要多少内存有个预先估计。

空间复杂度是考虑程序运行时占用内存的大小，而不是可执行文件的大小。

不要以为空间复杂度就已经精准的掌握了程序的内存使用大小，很多因素会影响程序真正内存使用大小，例如编译器的内存对齐，编程语言容器的底层实现等等这些都会影响到程序内存的开销。

所以空间复杂度是预先大体评估程序内存使用的大小。

14.空间复杂度是O(1)

以下空间复杂度是O(1):
代码可以看出，随着n的变化，所需开辟的内存空间并不会随着n的变化而变化。

即此算法空间复杂度为一个常量，所以表示为大O(1)。

int j = 0;
for (int i = 0; i < n; i++) {
    j++;
}

15.空间复杂度是O(n)

空间复杂度是O(n):
当消耗空间和输入参数n保持线性增长，这样的空间复杂度为O(n)
我们定义了一个数组出来，这个数组占用的大小为n，虽然有一个for循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，随着n的增大，开辟的内存大小呈线性增长，即 O(n)。

int* a = new int(n);
for (int i = 0; i < n; i++) {
    a[i] = i;
}

16.代码的内存消耗

1.不同的编程语言各自的内存管理方式,比如
所以python的基本数据类型所用的内存会要远大于存放纯数据类型所占的内存，例如，我们都知道存储int型数据需要四个字节，但是使用Python 申请一个对象来存放数据的话，所用空间要远大于四个字节
2.内存对齐