怎么判断一个算法的“好坏”程度——时间复杂度的计算

首先了解什么叫做数据结构。

数据结构，英文名称Data Structure，代表存储数据的不同方式。

接下来，了解一下算法。

算法，英文名称Algorithm，代表的是同一种问题的不同的解决方法。

算法往往针对的是特定的数据结构的：

• 不同的数据结构所使用的算法不同。
• 每种数据结构在特定的时间问题中的算法表现都不相同。

众所周知，在编程领域有很多的算法，虽然结果目的都一样，但是他们解决问题的思路却不尽相同，我们如何判断一个算法的优劣呢？

对于计算机来说，常用的测量标准有两个，一个是时间测算，一个是空间测算。通常我们使用这两种测量标准来判断算法的优劣。

• 时间测算：时间越少越好。
• 空间测算：空间浪费越少越好。

long before = System.currenTimeMillis();		//记录算法的开始时间
long after	= System.currenTimeMillis();		//记录算法的结束时间
System.out,println(after - before);

我们可以使用上述的代码来测算整个算法进行测算所耗费的时间，从而在时间测算这个角度判断一个算法的好坏。

在进行测算时，可能因为计算机的性能比较好而无法比较直观的发现两个算法之间细微的差别。

这个时候我们用到了一个方法，叫做"幅度不够，循环来凑"，没办法直观的看出算法之间的差别，那我们就将算法进行循环，这样就能体现出算法之间的区别了。

Big O标记

• 时间-问题(数据)规模
• 不考虑必须要做的操作
• 循环、赋初值、程序初始化…
• 不考虑常数项
• 2n–n
• 不考虑低次项
• n2+n – n2

学术上表示一个算法的优劣。先引入两个概念

时间复杂度：计算机解决问题的时间随着问题规模的扩大时间进行变化的规律。

空间复杂度：计算机解决问题时所占用的空间随着时间的扩大而进行变化的规律。

下面，根据例子来具体的了解时间复杂度与空间复杂度。

1、访问数组的某个位置的值

随着数组规模的扩大，观察所花费时间的变化。

访问数组最后一个位置的数，随着数组规模扩大，花费时间并不会发生改变。

数组要访问任意位置的值，所需要计算的是数组的偏移量，都是计算偏移量需要花费的时间。这是必须要做的操作。

这时，我们把这个算法的时间复杂度称之为O(1)。表示这个时间复杂度是一个常数，无论数组规模如何扩大，所花费的时间都是一个常数。

2、访问链表的某个位置的值

根据上面的例子，我们不难得出：访问链表的第一个数据的时间复杂度是O(1)，但是，在测算时间复杂度的时候，我们所考虑的都是最坏情况下的时间复杂度。

所以，我们对访问链表测算时间复杂度的情况是访问链表的最后一个值。

因为在链表进行访问时，我们无论如何都需要从第一个数开始进行访问，这里我们就可以得出，访问第一个数的时间复杂度是O(1)，访问第100个数的时间复杂度是O(100)。由此，可以得出访问链表的某个位置的值的时间复杂度是O(n)。

O(n)表示的是：当数据规模扩大时，所花费的时间随着进行线性的扩大。

每种算法的时间复杂度不尽相同，有的是O(n2),有的是O(n3),还有O(log n)等等。

总结的不是很全面，这里有算法时间复杂度和空间复杂度的详细视频介绍，关注转发私信“算法”，即可获得视频。