算法时间复杂度及效率(二)

        今天我们来看下算法复杂度和效率的问题,在判断一个算法的效率时,操作数量中的常数项和其他次要项常常是可以忽略的,只需要关注最高阶项就能得出结论。那么我们如何用符号定性的判断算法的效率呢?算法的复杂度分为两部分:1、时间复杂度,即算法运行后对时间需求量的定性描述;2、空间复杂度,即算法运行后对空间需求量的定性描述

        数据结构重点关注的是算法的效率问题,因此,我们后面会集中于讨论算法的时间复杂度;但其使用的方法完全可以用于空间复杂度的判断!我们经常在进行算法的时间复杂度用大O表示法来进行分析。下来对此种方法进行说明,算法效率严重依赖于操作(Operation)数量;操作数量的估算可以作为时间复杂度的估算;在判断时首先关注操作数量的最高次项。如下:

算法时间复杂度及效率(二)

        下来我们来分析下常见的时间复杂度:

        1、线性阶时间复杂度:O(n)。如下:

算法时间复杂度及效率(二)

        2、对数阶时间复杂度:O(logn)。如下

算法时间复杂度及效率(二)

        3、平方阶时间复杂度:O(n²)。如下:

算法时间复杂度及效率(二)

        下来我们来看看常见的时间复杂度,如下图所示

算法时间复杂度及效率(二)

        常见的时间复杂度的比较,如下

算法时间复杂度及效率(二)

        下面我们通过实例来进行分析下,下面的函数程序复杂度是怎样的

int find(int a[], int n, int v)
{
    int ret = -1;
    
    for(int i=0; i<=n; i++)
    {
        if( a[i] == v )
        {
            ret = i;
            break;
        }
    }
    
    return ret;
}

        我们如果定义的数组 a[5] = {1, 2, 3, 4, 5}; 如果是 int min = find(a, 5, 1); 这种则是最好情况了,仅需执行 1 次循环,此时便是 O(1);如果是 int max = find(a, 5, 5);此时便是最坏的情况了,需要全部执行,此时便是 O(n)。那么此时算法的最好与最坏情况便体现出来了,当算法在最乖情况下仍然能满足需求时,可以推断,算法的最好情况和平均情况都满足需求。在以后没有进行特殊说明时,所分析算法的时间复杂度都是指最坏时间复杂度。

        算法的空间复杂度(Space Complexity),其定义为 S(n) = S(f(n))。其中 n 为算法的问题规模,f(n) 为空间使用函数,与 n 相关。推倒时间复杂度的方法同样适用于空间复杂度,例如,当算法所需要的空间是常数时,其空间复杂度为 S(1)。我么来看看下面这个程序的空间复杂度为多少

long sum1(int n)
{
    long ret = 0;
    int* array = new int[n];
    
    for(int i=0; i<n; i++)
    {
        array[i] = i + 1;
    }
    
    for(iunt i=0; i<n; i++)
    {
        ret += array[i];
    }
    
    delete[] array;
    
    return ret;
}

        我们看到第一行为 1,第三行的 ret 定义也为 1,指针数组 array 的定义其空间复杂度为 n,下面两个进行 for 循环的空间复杂度分别为 1。因此整个程序所需的单位内存为: n + 4;即空间复杂度:S(n+4) = S(n)。那么时间跟空间之间是否存在某种联系呢?在多数情况下,算法的时间复杂度更令人关注,因为现在的内存都很大。如果有必要的话,可以通过增加额外空间降低时间复杂度;同理,也可以增加算法的耗时降低空间复杂度。下来我们来看个空间换时间的示例代码,代码的背景是在 1-1000 中的某些数字搜组成的数组中,设计一个算法类找出出现次数最多的数字。

#include <iostream>

using namespace std;

void sreach(int a[], int len)
{
    int pi[1000] = {0};
    int max = 0;
    
    for(int i=0; i<len; i++)
    {
        pi[a[i] -1]++;
    }
    
    for(int i=0; i<1000; i++)
    {
        if( max < pi[i] )
        {
            max = pi[i];
        }
    }
    
    for(int i=0; i<1000; i++)
    {
        if( max == pi[i] )
        {
            cout << i + 1 << endl;
        }
    }
}

int main(int argc, char* argv[])
{
    int a[] = {1, 1, 3, 4, 5, 6, 6, 6, 3, 3};
    
    sreach(a, sizeof(a)/sizeof(*a));
    
    return 0;
}

        我们来看看打印结果

算法时间复杂度及效率(二)

        我们看到打印了 3 和 6,因为最大数 6 和 3 都出现了 3 次。那么此次我们的程序实现中函数的时间复杂度为 O(n)。那么问题来了,当两个算法的大 O 表示法相同时,是否意味着两个算法的效率完全相同呢?肯定是不相同的!通过今天对算法的时间复杂度和效率的学习,总结如下:1、时间复杂度是算法运行时对于时间的需求量;2、大 O 表示法用于描述算法的时间复杂度,它只关注操作数量的最高次项;3、常见的时间复杂度为:线性阶,平方阶和对数阶;4、一般而言,在工程中使用的算法其复杂度都不超过 O(n³);5、算法分析与设计时,重点考虑最坏情况下的时间复杂度,大 O 表示法用于适用于算法的空间复杂度;6、空间换时间是工程开发中常用的策略。

原创文章,作者:Maggie-Hunter,如若转载,请注明出处:https://blog.ytso.com/193544.html

(0)
上一篇 2021年11月15日
下一篇 2021年11月15日

相关推荐

发表回复

登录后才能评论