Daily Summary(89)

9.10_Data structure

1、算法

1. 定义：基于数据结构的一系列步骤
2. 特性：有效性，确定性，有穷性，输入，输出

2、算法分析：对算法效率的分析

算法效率：时间效率（时间复杂度）、空间效率（空间复杂度）
时间复杂度T(n)=O(f(n))

#include "stdio.h"
int main()  
{  
   int i, j, x = 0, sum = 0, n = 100;  /* 执行1次 */  
    for( i = 1; i <= n; i++)           /* 执行n+1次 */  
    {  
        sum = sum + i;               /* 执行n次 */     
        for( j = 1; j <= n; j++)    /* 执行n*(n+1)次 */  
	{  
	     x++;                /* 执行n*n次 */  
             sum = sum + x;      /* 执行n*n次 */  
         }  
     }  
     printf("%d", sum);          /* 执行1次 */  
}  

执行总次数 T(n) = 1 + n+1 + n +n*(n+1) + n*n + n*n + 1 = 3n² + 3n + 3
算法时间复杂度表示为：O( n² )

9.10_Discrete

1、等值式：若等价式是重言式，则A，B等值，记A⇔B

２、重要等值式※

3. 简单析取式：仅由有限个命题变项或其否定构成的析取式
4. 简单合取式：仅由有限个命题变项或其否定构成的合取式
5. 析取范式：仅由有限个简单合取式构成的析取式
6. 合取范式：仅由有限个简单析取式构成的合取式
7. 极小项：合取式，每个变量按顺序排列，只能取p或┐p
   比如三个变元p，q，ｒ就有８个极小项：
   
8. 极大项：析取式，每个变量按顺序排列，只能取p或┐p
9. 主析取范式：简单合取式全是极小项
10. 主析合范式：简单析取式全是极大项

定理：任一命题都有唯一的主析取范式和主合取范式