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²)
网友评论