算法的时间复杂度分析

时间复杂度的定义

一个好的算法往往可以使程序运行的更快，衡量一个算法的好坏往往将算法效率和存储空间作为重要依据。算法的效率需要通过算法编制的程序在计算机上的运行时间来衡量，存储空间需求通过算法在执行过程中所占用的最大存储空间来衡量。本节主要介绍算法设计的要求、算法效率评价、算法的时间复杂度及算法的空间复杂。

在进行算法分析时，语句总的执行次数T(n)是关于问题规在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作T(n)=O(f(n))。

一般情况下，随着n的增大，T(n)的增长较慢的算法为最优的算法。

算法时间复杂度的分析

阅读如下代码：

以下代码分别输出了一个数字，一个一维数组和一个乘法口诀表：

#include <iostream>

using namespace std;

const int n = 10; 

int printNumber(int);
int printArray(int *); 
int printMultiTable();

int main()
{
    int data[] = {1,2,3,4,5,6,7,8,9,10};
    cout <<  endl;
    cout << "输出一个数字，仅仅一条语句，执行次数为" << printNumber(n) << endl;    
    cout <<  endl;
    cout << "遍历一个一位数组，数组元素个数为10,执行次数为" << printArray(data) << endl;    
    cout <<  endl;
    cout << "遍历一个一位数组，数组元素个数为10,执行次数为" << printMultiTable() << endl;    
    return 0;
}

//输出一个数字，返回执行次数
int printNumber(int number)
{
    cout << number << endl;
    return 1;
}

//遍历输出一个一维数组，返回执行次数
int printArray(int* data_1d)
{
    int count = 1;
    for(int i=0; i<10; i++)
    {   

        if(i>0)
        {
            cout << " ";
        }
        cout << data_1d[i];
        count++;
    }   
    cout << endl;
    return count;
}

//输出一个10以内的乘法口诀表，返回执行次数
int printMultiTable()
{
    int count = 1;
    for(int i=1; i<=n; i++)
    {   
        for(int j=1; j<=i; j++)
        {
            count++;
            cout << j << "*" << i << "=" << i*j << "\t";
        }
        cout << endl;
    }   
    cout <<endl;
    return count;
}

代码输出结果：

image

程序分别输出的执行次数为：

以上代码还不够直观，那么我们分别用两种方法来实现一下高斯算法：

include <iostream>

using namespace std;

int normMethod(int);
int gaussMethod(int);

int main()
{
    int lim;
    cout << "输入算法最大限定值 n = ";
    cin >> lim;
    cout << "普通算法执行次数：" << normMethod(lim) << endl;
    cout << "高斯算法执行次数：" << gaussMethod(lim) << endl;
    return 0;
}

//普通算法
int normMethod(int n)
{
    int count = 0;
    int result = 0;
    for(int i=1; i<=n; i++)
    {   
        result+=i;
        count++;
    }   
    cout << result << endl;
    return count;
}

//高斯算法
int gaussMethod(int n)
{
    int count = 1;
    int result = n * (n+1)/2;
    cout << result << endl;
    return count; 
}

运行结果：

image

高斯算法的实现，很好（也很简单）的体现了算法的时间复杂度问题；

普通算法的时间复杂度为 O(n)
高斯算法的时间复杂度为 O(1)

所以说，高斯算法是一个好算法!

当然，常见的多层循环嵌套的算法复杂度一般都会呈指数级增长

O(N^2)

O(N^3)

....

然而，在很多情况下，各种输入数据集出现的概率难以确定，算法的平均复杂度也就难以确定。因此，另一种更可行也更为常用的办法是讨论算法在最坏情况下的时间复杂度，即分析最坏情况以估算算法执行时间的上界.例如冒泡排序的最坏时间复杂度为数组a中初始序列为从大到小有序，则冒泡排序算法在最坏情况下的时间复杂度为T（n）=O（n2）。

算法的时间复杂度分析