算法基础

基本概念

算法的基本特性：

1. 输入输出

2. 有穷性

3. 确定性

4. 可行性

算法的基本要求：

1. 正确性

2. 可读性

3. 健壮性

4. 低时间/空间复杂度

算法分析：

对计算机运行某算法时所需的时间和存储资源上进行分析，包括时间复杂度分析和空间复杂度分析

基本语句：

执行次数与整个算法的执行次数成正比——贡献最大，最重要的语句

数据规模：

表征算法处理数据的大小，通常为输入数据的大小或总循环次数

//1
int i,sum=0,n=100;  
//n+1
for(i=1;i<=n;i++){
  //n
  sum=sum+1;
}

执行了1+n+n+1次，即T(n)=2n+2，若n=5，则执行了12次

时间复杂度：

基本语句执行的次数，通常用T(n)表示

渐近时间复杂度：

时间复杂度T(n)的阶，用O表示，如T(n)=4+n^2 :: O(n^2)

获取T(n)中最高阶项 的方法，即根据T(n)求O的方法：

1. 用常数1取代所有加法常数

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

3. 若最高项不为1，则去除与该项相乘的乘数

example：

平方阶

for i=0 i<n i++
  for j=i j<n j++
    ...

当i=0时，内层循环执行n次，当i=1时，执行了n-1次，当n=n-1时，执行了1次，所以内层循环：

T(n)=n+...+1= T(n)[for] + n*n + n *(n-1) /2 *1 => O(n)=n^2

对数阶

while(i<n)
  i=i*2

2^x>n跳出循环，所以O(n)=log2n

递推算法时间复杂度的求法

如：T(n)=2T(n-1)+1,T(1)=3

T(n)=2T(n-1)+1
      =2[2T(n-1-1)+1]+1  <=  T(n-1)=2[T(n-1-1)+1]
        =2^2T(n-2)+2
          =2^2[2T(n-2-1)+1]+2
            =2^3T(n-3)+3
              =......
                =2^(n-2)[2T(n-(n-2)-1)+1]+n-2
                  =2^(n-1)T(1)+n-1
                    =3·2n-1+n-1=(3/2)·2^n+n-1
                      =O(2^n)

公式法