算法竞赛之评估算法性能

利用大O表示法评估算法复杂度

评估算法性能评估什么?

1.时间:(程序运行所消耗的时间)

-问题的输入规模n和元素的访问次数f(n)的关系

时间复杂度:

在计算机科学中,算法的时间复杂度(Time complexity)是一个函数,它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。
时间复杂度-维基百科,自由的百科全书

简单的来说,时间复杂度就是算法的时间量度,常记做T(n)
时间复杂度常使用大O表示法表示,大O表示法是什么我会在下文解释。

2.空间:(程序运行所占用的空间)

-问题的输入规模n和元素的临时占用存储空间大小S(n)的关系

函数的渐进增长

输入规模n和元素的访问次数的关系我们用f(n)表示。
假设算法A:f(n)=2n+3
假设算法B:f(n)=3n+1
或许乍一看,我们会觉得算法A肯定要优于算法B的,那么实际是不是这样呢,我们可以枚举对比看看:

次数算法A算法B
n=154
n=277
n=3910
n=102331
n=100203301

我们可以看到在A在n=1时是不如是算法B的,在n=2时和算法B访问次数相同,而此后,随着n的逐渐增加,算法A总是优于算法B,我们把这种现象,称作函数的渐进增长

定义:在输入规模n没有限制的情况下,只要超过一个数值N,这个函数就总是大于另一个函数,我们称函数是是渐进增长的。给定两个函数f(n)和g(n),如果存在一个整数N,使得所有的n>N,f(n)总是大于g(n),那么我们说f(n)的渐进增长快于g(n)

大O表示法

大O符号(英语:Big O notation),又称为渐进符号,是用于描述函数渐近行为的数学符号。更确切地说,它是用另一个(通常更简单的)函数来描述一个函数数量级的渐近上界。在数学中,它一般用来刻画被截断的无穷级数尤其是渐近级数的剩余项;在计算机科学中,它在分析算法复杂性的方面非常有用。
大O符号-维基百科,自由的百科全书

大O表示法:算法的时间复杂度通常用大O符号表述,定义为T[n] = O(f(n))。称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n)。T(n)称为这一算法的“时间复杂度”。当输入量n逐渐加大时,时间复杂度的极限情形称为算法的“渐近时间复杂度”。

其实说白了也就一句话:大O表示法指出了最糟糕情况下的运行时间

那么,如何吧时间复杂度用大O表示法表示呐?
其实核心思想只有一个:忽略非主体部分(常数项,低阶项)而保留影响时间复杂度的主要部分
为什么这里要忽略常数和低阶项呐?我们可以就上面的例子,去掉和不去掉常数和低阶项来看看其对时间复杂度的影响。
算法A:f(n)=2n+3
算法B:f(n)=3n+1

次数算法A算法A(去常数阶)算法B算法B(去常数阶)
n=15243
n=27476
n=396109
n=1023203130
n=100200203301300

可以看到,诚然去掉之后值会变小,但从宏观的角度上来看,影响并不大,所以,我们可以去掉这些非主要部分而只关注最高次项的阶数。
那么,如何求大O阶呐,在这里我就直接贴《大话数据结构》中的截图呐,很好理解的.

常见的时间复杂度

常数阶:O(1)


无论n如何增长,语句都只执行3次,所以f(n)=3
由于f(n)无最高阶项,所以按照上面推导大O阶的方法:
T(n)=O(f(n))=O(3)=O(1)

线性阶:O(n)


f(n)=n+L(L为常数)
按照上面推导大O阶的方法:
T(n)=O(f(n))=O(n+1)=O(n)

对数阶:O(logn)


我们看代码可以发现这个循环结束由变量n控制,但是我们发现n每次都在平方,所以,最终循环执行的次数应该是由log2n决定的
所以f(n)=log2n,对于对数阶,无论底数为几,我们都规定其大O阶为O(logn)

平方阶:O(n^2)


两层for循环,结束变量都是n,所以f(n)=n^2
按照上面推导大O阶的方法:
T(n)=O(f(n))=O(n^2)

指数阶:O(2^n)

指数阶最典型的代表就是我在上一篇文章递归中写到的汉罗塔问题,其时间复杂度就为指数阶。
这种规模的问题随着n的增加,时间消耗会恐怖的增加。
例如:如取 N=64,最少需移动 264-1 次。即如果一秒钟能移动一块圆盘,仍将需 5849.42 亿年。目前按照宇宙大爆炸理论的推测,宇宙的年龄仅为 137 亿年。
在真实玩具中,一般 N=8;最少需移动 255 次。如果 N=10,最少需移动 1023 次。如果N=15,最少需移动32767次;这就是说,如果一个人从 3 岁到 99 岁,每天移动一块圆盘,他最多仅能移动 15 块。如果 N=20,最少需移动 1048575 次,即超过了一百万次。

常用时间复杂度所耗费的时间关系:


如图,从左往右,越往后,时间复杂度越高,算法性能越差。

性能对比:顺序查找和二分查找

顺序查找:O(n)

顺序查找按照序列原有顺序对数组进行遍历比较查询

二分查找:O(logn)

在计算机科学中,二分搜索(英语:binary search),也称折半搜索(英语:half-interval search)[1]、对数搜索(英语:logarithmic search)[2],是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
二分搜索算法-维基百科,自由的百科全书

性能对比:

这里我们使用clock函数来计算算法运行的时间

C++中的计时函数是clock(),而与其相关的数据类型是clock_t(头文件是time.h)。函数定义原型为:clock_t clock(void);

这个函数返回从“开启这个程序进程”到“程序中调用clock()函数”时之间的CPU时钟计时单元(clock tick)数,在MSDN中称之为挂钟时(wal-clock)。

#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
int efcz(const vector<int>& nums, int start, int end, const int& find)
{
    if (start > end) return -1;//递归出口
    int mid = start + ((end - start) >> 1);
    if (find < nums[mid])//分支递归
    {
        return efcz(nums, start, mid - 1, find);
    }
    else if (find > nums[mid])
    {
        return efcz(nums, mid + 1, end, find);
    }
    else
    {
        return mid;//返回结果
    }
}

int sxcz(const vector<int> nums, int start, const int& end, const int& find)
{
    if (start > end) return -1;//递归出口
    if (nums[start] == find) return  start;//递归出口
    return sxcz(nums, start + 1, end, find);

}

int main()
{
    clock_t start, end;
    vector<int>input;
    for (int i = 0; i < 10000000; i++)//构造数组
    {
        input.push_back(i);
    }
    input.push_back(233333333);//构造最坏的情况,将目标数字放在末尾
    start = clock();//计时器
    cout <<"二分查找查找到的下标:" <<efcz(input, 0, 10000000, 233333333) << endl;;
    end = clock();//计时结束
    cout << "二分查找的运行时间:" << end - start<<"ms"<<endl;//计算差值
    start = clock();;//计时器
    const int find = 233333333;//本来一开始用递归写的结果爆栈了:(
    for (int i = 0; i < input.size(); i++)
    {
        if (input[i] == find)
        {
            cout << "顺序查找到的下标:" <<i << endl;
            end = clock();//计时结束
            cout << "顺序查找的运行时间:" << end - start << "ms";//计算差值
        }
    }

}

运行结果:

emmmm,可以看到,优秀的算法和辣鸡算法的差距。。。不是一般的大。。。。

三种典递归形式算法的性能分析

递归问题的算法性能分析的两个要素:
1.子问题规模下降
2.子问题的答案的处理消耗的时间

阶乘递归算法的性能分析

int f(int n)
{
    if(n==1) return 1;
    return n*f(--n);
}

由上面讲的两个要素可以写出下式:
T(n)=T(n-1)+O(1)=T(n-1)
其中O(1)为乘法所消耗的。

斐波拉契数列算法的性能分析

求斐波拉契数列的递归算法是一个双分支递归(参见我之前写的关于递归的文章:算法竞赛中递归的基础运用)
递归每深一步实际上需要2次,可以写成下式:
T(n)=T(N-1)+T(N-2)+O(1)
其中O(1)为执行加法所消耗的,但是实际上,我没可以将T(n-1)和T(n-2)的差别忽略不计,所以可以写成:
T(n)=2T(N-1)+O(1)=O(2^n)

汉诺塔递归算法的性能分析

和斐波拉契问题类似,只不过
T(n)=2T(N-1)+O(1)=O(2^n)
而斐波拉契是
T(n)=T(N-1)+T(N-2)+O(1)

总结

emmm,这问题如果要进一步深入就是数学问题了,so,就不过多的涉及了,但是呐,总体上,递归问题的性能分析可以参考下表:

一下三个内容等博主做完查找和排序再一起说嗷

基础排序算法的性能对比

希尔排序的性能分析

排序算法的稳定性

Last modification:April 20th, 2019 at 07:43 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment