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

 

【声明】 

迎接转载,但求保留文章原来出处→_→ 

身壹号:http://www.cnblogs.com/smyhvae/

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

 

【正文】 

 

 

同等、数据结构涵盖的内容:

 

次、算法的基本概念:

1、算法的概念:

Algorithm,是指向特定问题求解步骤的一律种描述,它是命令的鲜序列,其中各级一样漫长指令表示一个要基本上个操作。

2、算法的风味:

  • 起穷性:指令序列是个别的
  • 明明:每条告句之义明确,无二义性
  • 大势:每条告句都答应以片的年月外形成
  • 输入:零个或者基本上个输入
  • 输出:一个还是多只出口

3、算法和程序的分:

程序:

  (program)程序是软件开发人员根据用户要求开发之、用程序设计语言描述的适合计算机执行之命(语句)序列。

先后包含的季单因素:

数据结构

算法

次第设计方

编程语言

次第与算法不同。程序是算法用某种程序设计语言的切切实实贯彻。程序可以免满足算法的发生穷性,比如操作系统为是同样种次,如果您肯,你的电脑可一直开着,保持操作系统的运作。

比如:

while(true)

{

...

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

 

4、程序、算法、软件内的干:

次:算法的微机实现。用某种编程语言实现。

算法:表示问题之消除。

软件:程序+文档

一般来说图所示:

次设计=数据结构+算 法

 

其三、数据类型:

1、数据类型:

凡恃一个价值的集和定义在集上之操作集合。例如:java的平头类型(Integer),就不但意味着整数数值的集纳,还连对整数类型进行的操作集合,加、减、乘、除、模等操作。

咱们司空见惯所依赖的数据类型是某种高级语言支持的骨干数据列。 
比如java的基本数据列:int、double、float、char等等。

Java中的数据类型:

2、抽象数据类型:

一个数学模型与定义在此模型上之均等组操作(由用户定义,用以代表以问题之数据模型)。

看起抽象数据类型和数据类型的概念基本相同。不同点在于:数据类型通常是指某种高级语言的,而抽象数据类型用户更规划,一栽概念。这里的”抽象”的意义在数学抽象。

  • 原子类型:比如整型
  • 一定聚合类型:比如复数,两单实数确定的次第构成
  • 然变换聚合类型:比如汽车类型,构成的成分是免确定的。(因为小轿车、大卡车的三结合是殊的)

抽象数据类型抽象的层系越强,那么可复用性也尤为强。比如:java中之Object是针对具备目标的纸上谈兵,那么即便好视作所有类的父类。

 

季、抽象数据类型的表示(代码举例):

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

下面分别就此C语言与java语言,来定义学生抽象数据类型。已领略学生的信如下:

学号:111222

姓名:生命壹号

性别:男

出生日期:1991-11

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

电子邮箱:smyhvae@163.com

 

1、用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;    
}

 运行效果:

 

 2、用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 } 

运转效果如下:

  

五、算法的计划性目标:

1、算法的筹划目标:

(1)正确性:满足实际问题之解除,基本对象。

(2)可读性:有利于人口失去了解算法。

(3)健壮性:输入非法数据,能适合做出处理,不起莫名其妙的输出。

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

2、算法性能指标:

(1)算法的时光效率呢号称时间复杂度。

(2)算法的半空中效率呢叫做空中复杂度。

(3)同一问题可用不同算法解决,而一个算法的身分好坏将震慑及算法乃至程序的频率。算法分析的目的在选择适当算法和改善算法。一个算法的褒贬要从时间复杂度和空中复杂度来考虑

(4)算法时间的高效性和空间的高效性通常是矛盾的。所有一般只有会取一个平衡点。(这里体现的凡同等种植哲学思想,研究计算机,不纵研究时跟空间的概念嘛,鱼与熊掌不可兼得啊)

(5)通常咱们设程序运行在内存中,且内存容量足够使用,所以再次多之是讨论时间复杂度。

 

六、算法的日复杂度:

算法的辰复杂度反映了算法执行之时空长短。度量一个算法在计算机上推行之时刻便发生一定量栽方式:

  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))
为算法的渐进时间复杂度,简称时间复杂度。看下图就是知道:

情亦然: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
     }
   }
 }

 上方代码中:

  

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

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

 分析:

  

例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-1浅遍历,则要进行n(n-1)/2次较和记录移动,此时冒泡排序算法的时刻复杂度T(n)=O(n2)。

 

3、时间复杂度的轻重关系:

以下六种植计算算法时间之几近项式是不过常用之。其干也:

指数日的关联呢:

当n取很挺之价值时,指数日算法和多项式时间算法在所需要时间上非常悬殊。

小知识:

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

 

七、算法的半空中复杂度:

空间复杂度是依赖算法在运转期间所要之内存空间的数码级。记作: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)

 

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