数据结构（一）：结构概念 与 算法概念 及 时间复杂度

数据结构概念

• 数据结构分为：逻辑结构、物理结构

逻辑结构

• 集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系
• 线性结构：数据元素之间是一对一的关系
• 树形结构：树形结构中元素之间存在一种一对多的层次关系
• 图形结构：元素是多对多的关系

物理结构（存储结构）

• 顺序存储：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的
• 链式存储：把数据元素存放在任意存储单元里，这组存储单元可以是连续的，也可以是不连续的，通过指针找到下一个存放的地址

算法概念

• 假设现在要写一个求1+2+3+4+…..+100的程序

int num = 0;
for (int i=1;i<=100;i++){
    num+=i;
}
System.out.println(num);

• 上面算法需要循环100次，当要求加到100000时，循环次数越多计算结果越慢，而采用高斯算法

int sum = 0, i = 1000000;
sum = (1 + i) * i / 2;
System.out.println(sum);

yBeXK.png

算法效率度量方法

• 事后度量法：通过计算算法开始时间与结束时间
• 事前分析估算法：分析程序执行代码次数（行数），优秀的算法相比普通算法根据问题输入规模 n 的大小，随着 n 的值越大，时间效率上的差异就越大

函数的渐进增长

• 假设有算法A与算法B：
  • 算法A----要做2n+3次操作（如执行完一个n次的循环，然后又执行一个n次的循环，最后执行3次赋值运算）
  • 算法B----要做3n+1次操作
  • 当 n>2 时，算法A就开始优于算法B，随着时间增加，算法A比算法B越来越好
• 在实际算法变化中，我们常忽略这些加法常数

算法时间长度

• 更多的例子：http://blog.csdn.net/zolalad/article/details/11848739
• 在进行算法分析时
  • 算法执行次数写为T（n），n是问题规模
  • 从而推导算法时间复杂度记作：T(n) = O(f(n))
  • 用大写的O( )体现算法时间复杂度，随着n增大，T(n)增长最慢为最优算法

推导大O的方法

• 用常数1取代运行时间中所有加法常数
• 在修改后的运行次数函数中，只保留最高阶项
• 如果最高阶项存在且不是为1，则去除常数项

常数阶

• 该算法运行次数为 f(n) = 3，根据推到大O方法，将常数项3改为1，该算法时间复杂度为 O(1)

int sum = 0, i = 1000000;   /*执行一次*/
sum = (1 + i) * i / 2;      /*执行一次*/
System.out.println(sum);    /*执行一次*/

线性阶

• 确定算法的阶次，分析算法的复杂度，关键是分析循环结构的运行情况，下面代码时间复杂度为 O(n)，因为循环体中的代码要执行 n 次

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

对数阶

• 下面代码每次会执行直到 count > n，每次执行完 count 会乘以 2，得 2的x次方=n 得到 x=log2n，该循环复杂程度为O(logn)

int count = 1;
while(count < n){
    count = count * 2;
    /* 时间复杂度为 O(1) 的程序步骤序列 */
}

平方阶

• 单个循环时间复杂度为 O(n)，而在循环嵌套内两个循环都执行 n ，则为 O(n的2次方)，如下面代码

int i,j,n = 200;
for(i = 0;i < n;i++){
    for（j = 0;j < n;j++）{
        // 时间复杂度为平方阶 O(n的2次方)
    }
}

• 若外循环次数为m，内循环次数为n，则时间复杂度为 O(m*n)

int i, j, m = 300, n = 200;
for (i = 0; i < m; i++) {
    for (j = 0; j < n; j++) {
        // 时间复杂度为 O(m*n)
    }
}

• 下面代码调用了一个函数，函数的时间复杂度为O(1)，所以整体时间复杂度为O(n)

public static void main(String[] args){
    int i,n = 200;
    for(i = 0;i < n;i++){
        fun();
    }
}
public static void fun(){
    System.out.println();
}

常见的时间复杂度

• 复杂度大小顺序为：O(1) < O(logn) < O(n) < O(nlogn) < O(n的平方) < O(n的立方) < O(2的n次方) < O(n!) < O(n的n次方)

执行次数函数	阶	非正式术语
12	O(1)	常数阶
2n+3	O(n)	线性阶
3*(n平方)+2n+1	O(n的平方)	平方阶
5log2n+20	O(logn)	对数阶
2n+3nlog2n+19	O(nlogn)	nlogn阶
6n的3次方+2n的平方+3n+4	O(n的立方)	立方阶
2的n次方	O(2的n次方)	指数阶