数据结构Java实现01—-算法概述

 

【声明】 

欢迎转发,但请保留小说原来出处→_→ 

生命壹号:http://www.cnblogs.com/smyhvae/

文章来源:http://www.cnblogs.com/smyhvae/p/4724692.html

 

【正文】 

 

 

壹 、数据结构涵盖的始末:

图片 1

 

贰 、算法的基本概念:

① 、算法的定义:

Algorithm,是对一定问题求解步骤的一种描述,它是命令的星星点点类别,其中每一条指令表示3个仍然多少个操作。

二 、算法的性状:

  • 西周性:指令体系是不难的
  • 同理可得:每条语句的含义显然,无二义性
  • 方向:每条语句都应在简单的日子内做到
  • 输入:零个依然几个输入
  • 出口:3个或然多个出口

三 、算法与程序的分别:

程序:

  (program)程序是软件开发人士依据用户供给开发的、用程序设计语言讲述的契合总计机执行的授命(语句)类别。

程序蕴含的两个要素:

数据结构

算法

程序设计艺术

编制程序语言

次第与算法分歧。程序是算法用某种程序设计语言的具体贯彻。程序能够不满意算法的西周性,比如操作系统也是一种程序,假设你愿意,你的总括机能够向来开着,保持操作系统的运作。

比如:

while(true)

{

...

} //是一段程序,但不是一个算法

 

肆 、程序、算法、软件之间的关联:

程序:算法的微型总计机完成。用某种编制程序语言达成。

算法:表示难题的解。

软件:程序+文档

如下图所示:

图片 2

程序设计=数据结构+算 法

 

③ 、数据类型:

壹 、数据类型:

是指3个值的汇集和定义在汇聚上的操作集合。例如:java的平头类型(Integer),就不光意味着整数数值的集结,还包蕴对整数类型实行的操作集合,加、减、乘、除、模等操作。

咱俩平常所指的数据类型是某种高级语言协助的着力数据类型。 
比如java的为主数据类型:int、double、float、char等等。

Java中的数据类型:

图片 3

贰 、抽象数据类型:

二个数学模型以及定义在那个模型上的一组操作(由用户定义,用以代表应用难点的数据模型)。

看起来抽象数据类型和数据类型的概念基本相同。差别点在于:数据类型常常是指某种高级语言的,而抽象数据类型用户重新规划,一种概念。那里的”抽象”的意思在于数学抽象。

  • 原子类型:比如整型
  • 永恒聚合类型:比如复数,五个实数鲜明的次第构成
  • 可变聚合类型:比如小车项目,构成的成份是不鲜明的。(因为小汽车、大卡车的整合是差异的)

抽象数据类型抽象的层系越高,那么可复用性也越高。比如:java中的Object是对具备目的的望梅止渴,那么就足以看成全数类的父类。

 

④ 、抽象数据类型的象征(代码举例):

  • C语言使用结构体
  • Java语言应用类

上面分别用C语言与java语言,来定义学生抽象数据类型。已知学生的音信如下:

学号:111222

姓名:生命壹号

性别:男

出生日期:1991-11

专业:电子与通信工程(计算机方向)

电子邮箱:smyhvae@163.com

 

壹 、用C代码定义二个上学的小孩子类:

test1.c:

#include <stdio.h>

//日期结构体
typedef struct 
{
  int year;//年
  int month;//月
  int day;//日      
}Date; 

//学生结构体 
typedef struct
{
  char sid[20];//学号
  char name[20];//姓名
  char gender;//性别
  Date birthday;//出生日期 
  char contact[50];//联系方式         
}Students;

void PrintStudentsInfo(Students s)
{
   printf("学号:%s\n",s.sid); 
   printf("姓名:%s\n",s.name);
   printf("性别:%c\n",s.gender);
   printf("出生日期:%d-%d-%d\n",s.birthday.year,s.birthday.month,s.birthday.day);
   printf("联系方式:%s\n",s.contact);      
}

int main()
{
  Students s1;//生成一个学生对象
  Date d1;
  d1.year = 1995;
  d1.month = 6;
  d1.day =30;
  strcpy(s1.sid,"S0001");
  strcpy(s1.name,"张三丰");
  strcpy(s1.contact,"西安市高新四路50号");
  s1.gender = 'M'; 
  s1.birthday = d1;
  PrintStudentsInfo(s1);
  getch();
  return 0;    
}

 运维作效果果:

图片 4

 

 ② 、用Java代码定义叁个学生类:

(1)Student.java:

 1 package test1;
 2 
 3 import java.text.SimpleDateFormat;
 4 import java.util.Date;
 5 
 6 /**
 7  * Created by smyhvae on 2015/8/12.
 8  */
 9 public class Student {
10     String num; //学号
11     String name; //姓名
12     char sex; //性别
13     Date birthday; //出生日期
14     String contact; //联系方式
15 
16     public String getNum() {
17         return num;
18     }
19 
20     public void setNum(String num) {
21         this.num = num;
22     }
23 
24     public String getName() {
25         return name;
26     }
27 
28     public void setName(String name) {
29         this.name = name;
30     }
31 
32     public char getSex() {
33         return sex;
34     }
35 
36     public void setSex(char sex) {
37         this.sex = sex;
38     }
39 
40     public Date getBirthday() {
41         return birthday;
42     }
43 
44     public void setBirthday(Date birthday) {
45         this.birthday = birthday;
46     }
47 
48     public String getContact() {
49         return contact;
50     }
51 
52     public void setContact(String contact) {
53         this.contact = contact;
54     }
55 
56     @Override
57     public String toString() {
58 
59         SimpleDateFormat sdf = new SimpleDateFormat("YYYY-mm-dd"); //将Date日期转化为String字符串打印出来
60 
61         return "Student{" +
62                 "num='" + num + '\'' +
63                 ", name='" + name + '\'' +
64                 ", sex=" + sex +
65                 ", birthday=" + sdf.format(birthday) +
66                 ", contact='" + contact + '\'' +
67                 '}';
68     }
69 
70 }

 

(2)JavaTest.java:(给学员类赋值并打字与印刷出来)

 1 package test1;
 2 
 3 import java.text.ParseException;
 4 import java.util.Calendar;
 5 import java.util.Date;
 6 
 7 /**
 8  * Created by smyhvae on 2015/8/12.
 9  */
10 public class JavaTest {
11 
12     public static void main(String[] args) throws ParseException {
13 
14         Student s = new Student();
15         s.setNum("111222");
16         s.setName("生命壹号");
17         s.setSex('男');  //这里面赋值可以用中文
18         s.setContact("smyhvae@163.com");
19 
20         Calendar calendar = Calendar.getInstance();
21         calendar.set(1991, 11, 28);
22         Date date = calendar.getTime();
23         s.setBirthday(date);
24 
25         System.out.println(s.toString());
26 
27     }
28 
29 } 

运营效果如下:

图片 5

  

五 、算法的安排目的:

① 、算法的规划指标:

(1)正确性:满意实际难题的解,基本对象。

(2)可读性:有利于人去明白算法。

(3)健壮性:输入违法数据,能方便做出处理,不发出莫明其妙的出口。

(4)高效性:包罗时间的高效性(时刻复杂度)和空中的高效性(空中复杂度)。

二 、算法品质指标:

(1)算法的小时功效也称之为时间复杂度。

(2)算法的空中作用也号称空中复杂度。

(3)同一难题可用分裂算法化解,而贰个算法的成色好坏将影响到算法乃至程序的成效。算法分析的意在采取合适算法和改良算法。2个算法的评说重点从岁月复杂度和空中复杂度来设想

(4)算法时间的高效性和空中的高效性日常是争辩的。全数一般只会取3个平衡点。(那里反映的是一种艺术学思想,斟酌总括机,不正是商讨时间和空中的定义嘛,鱼与熊掌不可兼得啊)

(5)常常大家如若程序运行在内存中,且内部存款和储蓄器体量丰裕使用,所以越来越多的是研讨时间复杂度。

 

⑥ 、算法的年华复杂度:

算法的岁月复杂度反映了算法执行的岁月长度。衡量1个算法在总计机上举办的时间经常有二种办法:

  1.事后总结法:

  2.在此以前分析法:(常用)

    编写算法使用的高档语言

    编制程序产生的机器语言代码品质

    机器指令执行进程

    难点规模

注:算法的时日复杂度是由最深层嵌套语句的频度决定的。

 

2、O()函数:

  表示算法的年华功能与算法所处理的多少成分个数n函数关系的最常用函数,即O()函数。

定义:

  一般景色下,算法中基本操作重复执行的次数是题材规模n的某些函数,用T(n)表示,若有有些帮忙函数f(n),使妥贴n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))
为算法的渐进时间复杂度,简称时间复杂度。看下图便知:

图片 6

图片 7

情景一:T(n)与难题规模n非亲非故

当算法的光阴复杂度T(n)与题材规模n毫无干系时,此时算法的时光复杂度T(n)=O(1)。

 

情状二:T(n)与题材规模n有关

例1:设数组a和b在前底部分已经赋值,求如下几个n阶矩阵相乘算法的时刻复杂度:

for(i=0;i<n;i++)
 {
   for(j=0;j<n;j++)
   {
     c[i][j]=0;  //基本语句1
     for(k=0;k<n;k++)
     {
        c[i][j]=c[i][j]+a[i][k]*b[k][j];//基本语句2
     }
   }
 }

 上方代码中:

图片 8

  

例2:设n为如下算法处理的数目元素个数,求算法时间复杂度。代码如下:

for(i=1;i<=n;i=i*2)
{
   System.out.println(i);
}

 分析:

图片 9

  

例3:分析冒泡排序算法的岁月复杂度。代码如下:

//冒泡排序算法
    public static void bubbleSort(int[] data) {

        if (data == null) {
            return;
        }

        for (int i = 0; i < data.length - 1; i++) {
            boolean flag = false;

            for (int j = 0; j < data.length - 1 - i; j++) {
                if (data[j] > data[j + 1]) {
                    int temp = data[j];
                    data[j] = data[j + 1];
                    data[j + 1] = temp;
                    flag = true;
                }
            }

            if (!flag) {
                return;
            }
        }
    }

 时间复杂度分析:

(1)最佳状态下,冒泡排序算法只要求遍历二遍就能分明数组已经排序好了,此时的光阴复杂度为O(n);

(2)最差处境下,要求展开n-一次遍历,则需实行n(n-1)/二遍比较和记录移动,此时冒泡排序算法的小时复杂度T(n)=O(n2)。

 

三 、时间复杂度的大小关系:

以下各种总计算法时间的多项式是最常用的。其涉及为:

图片 10

指数时间的关系为:

图片 11

当n取相当的大的值时,指数时间算法和多项式时间算法在所需时间上非凡悬殊。

小知识:

NP(nondeterministic
polynomial)标题:是指算法复杂度难以用多项式表示的难题,算法复杂度平日是n的指数级,常规算法很难求解。

 

7、算法的空中复杂度:

空中复杂度是指算法在运维时期所急需的内部存款和储蓄器空间的多寡级。记作:S(n)=O(f(n)),当中n为难题的层面(或大小)。            

注:由于大部分算法的空间复杂度难题并不严重,并且算法的上空复杂度分析方法和算法的年月复杂度分析方法基本相同,所以一般数据结构只谈谈算法的岁月复杂度,不切磋算法的半空中复杂度。

代码举例:分析如下算法的长空复杂度

static void reserse(int[] a,int[] b)
{
   int n= a.length;
   for(int i=0;i<n;i++)
   {
      b[i]=a[n-1-i];
   }
} 

下边代码中,当程序调用reserse(a,b)函数时,要分配的内部存款和储蓄器空间包含:引用a,引用b,局部变量n和一部分变量i;

就此f(n)=c;个中c为常量。所以该算法的空间复杂度S(n)=O(1)。

 

八、总结:

算法的光阴复杂度和四个成分有关:算法中的最大嵌套循环层数;最大嵌套循环结构中年老年是循环的次数。

貌似的话,具有多项式时间复杂度的算法是还可以的;具有指数(不是对数)时间复杂度的算法,惟有当n充足小时才方可运用。一般效率较好的算法要控制在O(N)抑或O(log2
N)

 

手有玫瑰,赠人余香。支付宝扫一扫吧:

图片 12

 

相关文章