算法的基本概念

1.算法：

        算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

        算法具有五个基本特性：输入，输出，有穷性，确定性和可行性。

        a.算法具有零个或多个输入，至少有一个或多个输出。

        b.有穷性：指算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每个步骤都在可接受的时间内完成。

        c.确定性：算法的每一个步骤都具有确定的含义，不会出现二义性。

        d.可行性：算法的每一步都必须是可行的，也就是说，每一步都能够执行有限次数完成。

        算法设计要求：

        a.正确性，b.可读性，c.健壮性，d.时间效率高和存储量低。好的算法应具有正确性，可读性，健壮性，高效率，和低存储的特征。

2.算法的时间复杂度：

        算法的时间复杂度，也就是算法的时间量度，记做T(n)=O(f(n))。他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。

        推到大O阶方法：

            a.用常数1取代运行时间中的所有假发常数。

            b.在修改后的运行次数函数中，只保留最高阶项。

            c.如果最高阶项存在且不是1，则去除与这个项相乘的常数得到的结果就是大O阶。

例：对数阶

        下面这段函数的时间复杂度

int  count = 1;

while  (count <n)

{

    count = count*2;

}

    由于每次count乘以2后，就距离n更近了一分，也就是说，有多少个2相乘后大于n，则就会退出循环。由2*=n得到log2n=x，所以这个循环的时间复杂度为O（logn）。

例2：平方阶

int i , j ;

for(i=0;i<n;i++)

{

    for(j=i;j<n;j++)

        {

......

    }

}

    当i=0时，内循环执行了n次才跳出循环，当i=1时，则执行了n-1次...当i=n-1时，执行了1次，所以总的执行次数为n+(n-1)+(n-2)+(n-3)+......+1=n(n+1)/2=n²/2+n/2。所以用推导大O阶方法，第一条，没有加法常数不予考虑；第二条，只保留最高阶项及n²/2，第三条，去除这个项相乘的常数，即二分之一，最终这段代码的时间复杂度为O(n²)。

例3：

n++ ;               //执行次数1

function(n);            //次数n

int i,j;

for(i=0; i<n; i++)            //执行次数n²

{

    function(i) ; 

}

for(i=0; i<n; i++)                //执行次数n(n+1)/2

{

    for(j=i; j<n; j++)

    {

..........

}

}

所以这个程序的执行次数为f(n)=1+n+n²+n(n+1)/2=3n²/2+3n/2+1,根据推导大O阶方法，最终得到这段代码的时间复杂度也是O(n²)