【算法与数据结构-1】时间复杂度-以斐波拉切为例子

2020/7/16 12:31:24 人评论 次浏览 分类:学习教程

目录:

【算法与数据结构-1】复杂度_以斐波拉切数例
【算法与数据结构-2】链表1-设计动态数组

一、概述

大O表示法:

  • o(1)<o(logn)<o(n)<o(nlogn)<o(n2)<o(n3)<o(2n)<o(n!)<o(nn) o(1)<o(logn)<o(n)<o(nlogn)<o(n^2)< o(n^3)<o(2^n)<o(n!)<o(n^n)

斐波拉切数列

  • 斐波拉切数列另外的名字是黄金分割数列,和生物细胞的分裂非常像,以指数级方式增长,fn=f(n-1)+f(n-2)且(n>=2,n属于N*)
  • 用到的算法1:递归
		if(n<=1) return n; //前两个特殊处理
		return fib1(n-1)+fib1(n-2);
  • 用到的算法2:
		if(n<=1) return n;
		int frist = 0;
		int second = 1;
		for(int i=0;i<n-1;i++) {
			int sum = frist + second;
			frist=second;
			second=sum;

二、实战

1、算法对比图

在这里插入图片描述

2、斐波拉切数例代码【配合大O表示法】

同一问题,不同算法实现后效率完全不同

package com.weiranyi.fib;
import java.lang.reflect.Array;
import com.weiranyi.fib.Times.Task;

/**
 * 斐波拉切数:
 * - 第三个=前两个之和
 *  - 0、1、1、2、3、5、8、13···
 */
public class Day01_fib {
	public static void main(String[] args) {
		/**
		* System.out.println(fib1(64));
		* 输入64时,结果一直不出来
		* 证明:算法有问题
		* */
		Times.test("算法1", new Task() {
			public void execute() {
				System.out.println(fib1(46));
			}
		});
		Times.test("算法2", new Task() {
			public void execute() {
				System.out.println(fib2(46));
			}
		});
	}
//算法1:递归
	public static int fib1(int n){
		/**
		*复杂度:
		*  大O表示法:O(2^n)
		*  看函数执行多少次
		*/
		if(n<=1) return n;
		return fib1(n-1)+fib1(n-2);
	}
//算法2:
	public static int fib2(int n){
		/**
		* 复杂度:
		* 1+1+1+1+(n-1)+(n-1)+(n-1)*(1+1+1)+1
		* 大O表示法:o(n)
		*/
		if(n<=1) return n;
		int frist = 0;
		int second = 1;
		for(int i=0;i<n-1;i++) {
			int sum = frist + second;
			frist=second;
			second=sum;
		}
		return second;
		
	}
}

3、代码中算法1与算法2函分析

1、从大O表示法抽象出的函数的函数图像上看:

算法1与算法2分析

2、对算法1单独分析

树状图分析算法

三、思考

  1. 实战算法没有考虑【健壮性】,如:加个非法输入判断
  2. 实战算法没有考虑【容错性】,如:加个数据类型的自动转换

四、结论

  • 同一问题,不同求解过程会影响到程序的执行效率
  • 能不用递归就尽量不用递归算法

相关资讯

    暂无相关的资讯...

共有访客发表了评论 网友评论

验证码: 看不清楚?
    -->