数据结构概述

1.1本章学习目标

• 什么是数据结构
• 为什么要使用数据结构
• 算法分析

 1.2 什么是数据结构

        对于什么是数据结构，不同的教材有不同的说法，也没有一个标准的定义。下面引用百度百科的说法：

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。详情参见：

http://baike.baidu.com/view/9900.htm

1.3为什么要使用数据结构

      这个，本人也勿用多说，之前听过某位高人说的一句话，当一个东西你怎么都理解不了的时候，试着放一放，不去纠结为什么要这么用呢？你先就这么用着，终有一天你会明白为什么会这么用了，你也不用担心我会不会明白的太晚，这是很多人的学习心得。

       很多公司面试的时候，总喜欢出各种数据结构的题，而且各位可以发现众多的面试题中，谈到数据结构的绝对不在少数！当然，如果你不懂数据结构，你照样也可以拿SSH写出程序，而且你个人感觉可能允许的还不错！就想修炼功夫一样，练就飞花摘叶之神功，需要的是内功的练习，普通的花拳绣腿，看起来的却华而不实。

1.4算法分析

     高质量软件的几个常见特征：

• 正确性
• 可靠性
• 健壮性
• 可用性(易用性)
• 可维护性
• 可重用性
• 可移植性
• 运行效率

算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。算法复杂度分为时间复杂度和空间复杂度。其作用： 时间复杂度是度量算法执行的时间长短；而空间复杂度是度量算法所需存储空间的大小，用大O表示法。下面主要探讨下时间复杂度的计算

时间复杂度的分析：

①循环的复杂度

例1.

1. for(int i=0;i<n;i++) {  
2.   //复杂度为O(1)的代码  
3. } 

要分析此算法的复杂度，就需要分析循环的运行。该循环体具有O(1)的复杂度，且该循环执行N次，即该复杂度为O(n).

例2.

下面的循环的复杂度就是对数级的，因为每循环一次，i的值就被乘以2，循环执行的次数为logn，当我们在算法复杂度中使用对数时，一般都是指以2为底数。因此下面的算法的复杂度为O(logn)

1. int i=0;  
2. while(i<n){  
3.    i*=2;  
4.    //复杂度为O(1)的代码  
5. } 

②嵌套循环的复杂度分析

 分析嵌套循环的复杂度时，则必须把外层循环和内存循环都考虑进来！因此可以很容易的算出下面的复杂度为O(n^2).

1. for(int i=0;i<n;i++) {  
2.         for(int j=0;j<n;j++) {  
3.             //复杂度为O(1)的代码  
4.         }  
5.     } 

③方法调用的复杂度分析

对于下面的算法复杂度的分析，就要先找到count方法的复杂度，如果count方法的复杂度为O(n)，因此下面的伏安法的复杂度为O(n^2).

1. for(int i=0;i<n;i++) {  
2.         count(i);  
3.     }  

④多种循环、的复杂度分析

下面的复杂度计算如下：O(n^2)+O(n)

忽略非主要阶次，因此得出算法复杂度为O(n^2)

1. public void test(){  
2.     for(int i=0;i<n;i++) {  
3.         for(int j=0;j<n;j++)  
4.         {  
5.             System.out.println("j"+j);  
6.         }   
7.     }  
8.     for(int j=0;j<n;j++)  
9.     {  
10.         System.out.println("j"+j);  
11.     }  
12.     } 

 时间复杂度按数量级递增排列，常见的时间复杂度有：

　　常数阶O(1),对数阶O(log2n),线性阶O(n),

　　线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),...，

下面附上各种排序算法的时间空间复杂度的比较表：

 本文转自 w156445045 51CTO博客，原文链接：http://blog.51cto.com/enetq/706732，如需转载请自行联系原作者