时间复杂度

简介

我们往往把一个算法的复杂度分为时间复杂度和空间复杂度，时间复杂度对应算法执行所需要的时间，空间复杂度对应所需要的内存，相对来讲空间代价肯定是比时间代价更小，所以算法的时间复杂度成为评价算法优劣的最重要的指标之一。

引用百度百科的介绍：“一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f (n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。”

总结

如果输入规模为n，那么算法的时间基本上可以用一个关于n的函数f(n)表示，时间复杂度T(n)=O(f(n)),f(n)仅保留最高次项，且舍去系数。

如算法执行所需时间f(n)=6n^3+2n+3,T(n)=O(f(n))=O(n^3)

例

线性查找：f(n)=n，T(n)=O(f(n))=O(n)

bool function(vector<int> vec,int tag)
{
    int n=vec.size();
    for(int i=0;i<n;i++)
    {
        if(vec[i]==tag)
            return true;
    }
    return false;
}

折半查找：f(n)=log(2)n，T(n)=O(f(n))=O(logn)

bool function(vector<int> vec,int tag)
{
    //vec是升序向量
    int first=0,last=vec.size()-1;
    int index=0;
    while(first<=last)
    {
        index=(first+last)/2;
        if(vec[index]>tag)
            last=index-1;
        else if(vec[index]>tag)
            first=index+1;
        else
            return true;
    }
    return false;
}