数据结构之时间复杂度

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。

那么我们应该如何去衡量不同算法之间的优劣呢?

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。

空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。

因此,评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而,有的时候时间和空间却又是「鱼和熊掌」,不可兼得的,那么我们就需要从中去取一个平衡点。

在网上可以找到很多的关于时间复杂度和空间复杂度的介绍,在这里我就不用专业术语讲解其理论,我会以通俗的语言介绍。

时间复杂度

时间复杂度,顾名思义讲的是一段程序所运行的时间。不过这里将的运行时间并不是实际上花费的时间,而是表示一个量的概念。比如常数时间、一次、二次。。。等等。下面我们介绍如何求一个程序段的时间复杂度:

在我们求时间复杂度之前,我们必须先了解什么是“原子操作”(可能不准确)。所谓的“原子操作”指的是花费时间在一个常数级别的运算。例如:

int i = 1, j = 2;
int c = i + j;

再比如:

int sum = 0;
for(int i = 0; i < 1000; i++)
    sum += i;

上面的两段程序可以都视为一个“原子操作0”。而我们所求的时间复杂度就是一段程序中,“原子操作”所执行的次数。例如:

int sum = 0;
for(int i = 0; i < n; i++)
{
    sum += i;//原子操作
}

其中累加运算就是一个“原子操作”,而这个操作执行次数为n,ze其时间复杂度为O(n);再比如:

int sum = 0;
for(int i = 0; i < n; i++)
    for(int j = 0; j < n; j++)
    {
          sum += i;//原子操作
          sum += j;//原子操作
    }

时间复杂度为O(2*n2)==O(n2)。

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

原子操作运行次数为1/2*n*(n-1),则时间复杂度为其最高项O(n2)。

空间复杂度

空间复杂度与时间复杂度求法相同,都是查看原子操作,只不过在这里查看原子操作开辟空间的量级,比如int i = 0代表单位空间,即O(1),而int n[m]的空间复杂度则为O(m),其中m不为常数。我们只需要将原子操作的空间量级乘以运行次数即可,例如:

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

空间复杂度为O(n2)*O(1)====O(n2)

int sum = 0;
for(int i = 0; i < n; i++)
    for(int j = i; j < n; j++)
    {
        int k[] = new int[m];
        }

空间复杂度为O(n2)*O(m)===O(m*n2).

———————————————————————–写在最后的话—————————————————

由于是考研的专业课是数据结构,并且也辅导过几届学生的数据结构,感觉能够用通俗易懂的语言给大家讲好数据结构,但这一章写下来还是挺乱的。应该说是很失败,写博客跟现场辅导还是有很大区别的,希望在以后能有所改进吧,也希望大家能多提意见,希望我写的博客对大家能有所帮助

    原文作者:LMRzero
    原文地址: https://blog.csdn.net/qq_16669583/article/details/90649216
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞