xinbiancheng.cn

java算法初体验和基本概念

本教程目前用java语言来讲解，像python之类的语言算法原理是一样的，如果需要看python版本的算法请点击，python算法

数据结构和算法的魅力

基本概念

度量算法的执行时间

空间复杂度

数据结构和算法的魅力

1、ArrayList和LinkedList

ArrayList底层是数组，查询快，插入慢，有移动的动作。

LinkedList底层是链表，插入快，查询慢。

Java算法体验代码如下：

package xinbiancheng.cn;

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
public class ExperienceAlgorithm {
public static void main(String[] args) {
	//当我们 在生成类的时候，忘记了产生 主 main方法 如何在Eclipse中快速添加main方法
	// 输入main 然后用快捷键 alt+/,就可以快速产生 main方法
	int frequency=100000;
	addLinkedList(frequency);
	addArrayList(frequency);
	
}
private static void addArrayList(int frequency)
{
	long begin = System.currentTimeMillis();
	List list = new ArrayList();
	for(int i=0; i<frequency;i++) {
		list.add(0,i);
	}
	long end = System.currentTimeMillis();
	System.out.println("ArrayList time=="+(end-begin)+"ms");
}
private static void addLinkedList(int frequency)
{
	long begin = System.currentTimeMillis();
	List list = new LinkedList();
	for(int i=0; i<frequency;i++) {
		list.add(0,i);
	}
	long end = System.currentTimeMillis();
	System.out.println("LinkedList time=="+(end-begin)+"ms");
}
}

ArrayList() 和 LinkedList() 运行的时间的结果如下：

LinkedList time==25ms
ArrayList time==2190ms

通过java从上面运行的结果来看，差距100倍，如果把frequency=100000，在增加10倍，或更多，差距就更大了，所以这个就是算法的魅力了，同样做一件事情，运算效率会差很多。

2、-1^n问题

编程求(-1)^0+(-1)^1+(-1)^2+......+(-1)^n

思路一：循环遍历求sum

思路二：当n为奇数时sum=-1,当n为偶数时sum=0

3、1到100求和问题

编程求1+2+3+......+100

思路一：循环遍历求sum

思路二：(1+n)*n/2

基本概念

数据结构(data structure)

数据结构是相互之间存在一种或多种特定关系的数据元素的集合

研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系

数据结构包括：线性结构和非线性结构

算法（algorithm）

是解题方案的准确而完整的描述，是一系列解决问题的清晰指令

算法代表着用系统的方法描述解决问题的策略机制

一个算法的优劣可以用时间复杂度和空间复杂度来衡量

度量算法的执行时间

度量一个程序（算法）执行时间的两种方法

  • 事后统计法

  • 事前估算法

统计某个算法的时间复杂度来度量方法的优越性

时间复杂度统计法属于事前估算法

时间频度T(n)

时间频度:一个算法花费的时间与算法中语句的执行次数成正比

一个算法中的语句执行次数称为语句频度或时间频度，记为T(n),n称为问题的规模

时间复杂度O(n)

某个函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))

T(n)和O(f(n))不同，但时间复杂度可能相同

O(f(n))为算法的渐进时间复杂度，简称时间复杂度

最坏时间复杂度

最坏情况下的时间复杂度称为最坏时间复杂度

一般讨论的时间复杂度均是最坏情况下的时间复杂度

最坏情况下的时间复杂度是算法在任何输入实例上运行时间的界限

平均时间复杂度

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，该算法的运行时间

平均时间复杂度和最坏时间复杂度是否一致和算法有关

空间复杂度

一个算法的空间复杂度(Space complexity)定义为该算法所耗费的存储空间，它也是问题规模n的函数

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的度量

在做算法分析时，主要讨论的是时间复杂度

从用户使用体验上看，更看重的是程序执行的速度

一些缓存产品(redis,memcache)和算法(基数排序)本质就是用空间换时间