【Java数据结构的实现】系列一数据结构概述

简介:

数据结构概述

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)的代码  

要分析此算法的复杂度,就需要分析循环的运行。该循环体具有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)的代码  

②嵌套循环的复杂度分析

 分析嵌套循环的复杂度时,则必须把外层循环和内存循环都考虑进来!因此可以很容易的算出下面的复杂度为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,如需转载请自行联系原作者


相关文章
|
1天前
|
消息中间件 存储 缓存
Java中的数据结构与算法优化攻略
Java中的数据结构与算法优化攻略
|
1天前
|
算法 Java
Java数据结构与算法:位运算之位移操作
Java数据结构与算法:位运算之位移操作
|
1天前
|
存储 算法 Java
Java数据结构与算法:线性数据结构之数组
Java数据结构与算法:线性数据结构之数组
|
1天前
|
算法 Java
Java数据结构与算法:字符串匹配算法之暴力匹配
Java数据结构与算法:字符串匹配算法之暴力匹配
|
1天前
|
算法 Java
Java数据结构与算法:位运算之与、或、异或运算
Java数据结构与算法:位运算之与、或、异或运算
|
1天前
|
算法 Java
Java数据结构与算法:字符串匹配算法之KMP算法
Java数据结构与算法:字符串匹配算法之KMP算法
|
1天前
|
数据采集 算法 Java
Java数据结构与算法:图算法之广度优先搜索(BFS)
Java数据结构与算法:图算法之广度优先搜索(BFS)
|
1天前
|
算法
【C/数据结构和算法】:栈和队列
【C/数据结构和算法】:栈和队列
6 1
|
5天前
|
C++
【洛谷 P1044】[NOIP2003 普及组] 栈 题解(递归+记忆化搜索)
**NOIP2003普及组栈问题**:给定操作数序列1到n,仅允许push(进栈)和pop(出栈)操作。目标是计算所有可能的输出序列总数。输入包含一个整数n(1≤n≤18)。示例输入3,输出5。当队列空时返回1,栈空则只能入栈,栈非空时可入栈或出栈。AC C++代码利用记忆化搜索求解。
8 1
|
7天前
|
算法
$停车场管理系统 栈与队列
$停车场管理系统 栈与队列
8 1