宽屏网站欣赏,南宁论坛,做网站外包,开发公司总结计划目录
一、数据结构的概念
1.1. 什么是数据结构
1.2. 算法与数据结构的关系
二、算法效率
三、时间复杂度
3.1. 大O的渐进表⽰法
3.2. 计算冒泡排序的时间复杂度
3.3. 计算二分查找的时间复杂度
四、空间复杂度
4.1. 空间复杂度
4.2. 冒泡排序的空间复杂度
4.3.…目录
一、数据结构的概念
1.1. 什么是数据结构
1.2. 算法与数据结构的关系
二、算法效率
三、时间复杂度
3.1. 大O的渐进表⽰法
3.2. 计算冒泡排序的时间复杂度
3.3. 计算二分查找的时间复杂度
四、空间复杂度
4.1. 空间复杂度
4.2. 冒泡排序的空间复杂度
4.3. 斐波那契数列的空间复杂度
五、学习时间复杂度和空间复杂度的好处 一、数据结构的概念
1.1. 什么是数据结构 什么是数据结构呢相信很多老铁尤其是非计算机专业的老铁还是第一次听说这个词。通俗地说数据结构就是在内存当中对我们的数据进行一个管理和建立数据见关系我们熟知的内存条如下图所示就是存储数据的介质我们对数据的管理就是存储在内存条上的。 计算机这个学科最重要的是做软件开发软件可以帮助我们实现各种功能比如我们微信好友列表里面表面上就是一堆姓名的数据透过计算机我们看到的只是01010而这些数据就存在内存条上。 1.2. 算法与数据结构的关系 算法就是定义良好的计算过程它取⼀个或⼀组的值为输⼊并产⽣出⼀个或⼀组值作 为输出。简单来说算法就是利用计算机处理问题的步骤比如我们对数据进行一个排名就要用到排序算法以及需要这个区域来进行排名就需要堆来实现。 那么数据结构与算法之间的关系呢二者相辅相成你中有我我中有你。解决一些算法问题需要用到数据结构实现一些数据结构时又需要用到一些算法。
二、算法效率 如何衡量⼀个算法的好坏就需要用到算法效率去衡量。算法效率分析分为两种第⼀种是时间效率第⼆种是空间效率。时间效率被称为时间复杂度⽽空 间效率被称作空间复杂度。时间复杂度主要衡量的是⼀个算法的运⾏速度⽽空间复杂度主要衡量⼀ 个算法所需要的额外空间。 通俗点说时间复杂度和空间复杂度用来衡量代码消耗资源开销的多少衡量的标准应该是与代码有关与运行的设备无关。
三、时间复杂度 ⼀个算法所花费的时间与其中语句的执⾏次数成正⽐例算法中的 基本操作的执⾏次数为算法的时间复杂度。站在数学的角度来看时间复杂度可以看作是计算关键操作的次数与使用问题规模的函数关系再对这个函数关系进行一个化简和近似。化简就是只取最高次项把最高次项的系数也忽略掉记作O() 。 下面博主将结合代码带大家来具体体会一下时间复杂度。
3.1. 大O的渐进表⽰法
import java.util.Scanner;public class Main {public static int func(int N){int count 0;for (int i 0; i N; i) {for (int j 0; j N; j) {count;}}for (int k 0; k 2*N; k) {count;}int M 10;while((M--)0){count;}return count;}public static void main(String[] args) {Scanner num new Scanner(System.in);int b num.nextInt();int a func(b);System.out.println(a);}
} 上面的基本操作就是count的自增那么count的被执行次数与N的函数关系就是。那么我们就要记作。
import java.util.Scanner;public class Main {public static int func(int N){int count 0;for (int i 0; i N; i) {for (int j 0; j N; j) {count;}}
/* for (int k 0; k 2*N; k) {count;}*/int M 10;while((M--)0){count;}return count;}public static void main(String[] args) {Scanner num new Scanner(System.in);int b num.nextInt();int a func(b);System.out.println(a);}
} 上面这段代码的函数关系是那么依旧是记作。随着N值的增大两个函数的值会越来越接近。 所以说计算时间复杂度一定要先找到核心的基本操作是什么。这个基本操作可能是打印、修改、比较或者是删除。 我们下面一段代码因为描述问题规模的方式不一定就只有一个变量也可以是多个。此时我们应该记作。
import java.util.Scanner;public class Main {public static int func2(int M,int N){int count 0;for (int k 0; k M; k) {count;}for (int k 0; k N; k) {count;}return count;}public static void main(String[] args) {Scanner num new Scanner(System.in);int m num.nextInt();int n num.nextInt();System.out.println(func2(m, n));}
} 我们再来看下面一段代码下面的时间复杂度就比较固定了基本操作的次数与N无关无论N是多少count永远被循环了100次。那么此时的时间复杂度要记作常数级时间复杂度。及时这里的i1亿时间复杂度照样是。
import java.util.Scanner;public class Main {public static int func3(int N){int count 0;for (int i 0; i 100; i) {count;}return count;}public static void main(String[] args) {Scanner num new Scanner(System.in);int a num.nextInt();System.out.println(func3(a));}
} 如果说出现了两段代码一个时间复杂度是另一个是那么不一定比慢有可能当N比较小时时间复杂度要比。所以说在这里要牢记时间复杂度衡量的是问题规模和时间的变化趋势不能直接决定快慢。
3.2. 计算冒泡排序的时间复杂度
public class Main {public static void BubbleSort(int[] arrays){for (int end arrays.length; end 0; end--) {boolean sorted true;for (int i 0; i end; i) {if(arrays[i-1] arrays[i]){Swap(arrays, i - 1, i);sorted false;}}if (sorted true){break;}}}
} 我们想要计算这个BubbleSort的时间复杂度同理首先也要搞清楚基本操作是什么。其中我们调用Swap方法进行交换的时候在里面是不涉及内嵌循环的所以计算时间复杂度的时候不用计算Swap内部的交换。我们先看外层循环起始end的值是数组的长度N内层循环呢由于end的值不固定当endN时i循环了N次当endN-1时i循环了N-1次。所以时间复杂度的计算就是结果就是。
3.3. 计算二分查找的时间复杂度
public class Main {public static int BinarySearch(int[] arrays,int value){int begin 0;int end arrays.length - 1;while(begin end){int mid begin ((end-begin) / 2);if (arrays[mid] value){begin mid 1;}else if(arrays[mid] value){end mid - 1;}else{return mid;}}return -1;}
} 二分查找每循环一次区间就会缩小一半当区间缩小为1的时候我们才得出“找到或者是没找到”的结论。我们可能说不好直接得出时间复杂度来那我们就利用特殊值法。当数组元素为8时最多要经历4次循环当数组元素为16时最多要经历5次循环。所以我们可以得出时间复杂度为。 对数级别的复杂度及时问题规模变得很大核心操作次数增长依然缓慢。 综合冒泡排序和二分查找的时间复杂度时准确地说要涉及到三种情况1.最好情况下最需要循环一次就能找到2.平均情况下循环一半的次数3.最坏情况下循环了最多次。
四、空间复杂度
4.1. 空间复杂度 空间复杂度是衡量代码运行中消耗的临时空间也就是我们的代码在运行时所创建的空间至运行结束被销毁的空间。比如一个数组长度为N在后续代码中并没有创建任何临时的空间。此时这个数组的空间复杂度就是常数级复杂度。
4.2. 冒泡排序的空间复杂度
public class Main {public static void BubbleSort(int[] arrays){for (int end arrays.length; end 0; end--) {boolean sorted true;for (int i 0; i end; i) {if(arrays[i-1] arrays[i]){Swap(arrays, i - 1, i);sorted false;}}if (sorted true){break;}}}
} 上面的代码都创建了三个临时变量sorted和i都创建了N次那么空间复杂度就是2N1也就是。但其实不是的因为空间和时间不一样时间是一去不复返的而空间是可以重复利用的都是销毁了前一个才创建下一个前一个和下一个共用同一块空间。一共三个临时变量所以空间复杂度就是。
4.3. 斐波那契数列的空间复杂度
int[] fibonacci(int n) {long[] fibArray new long[n 1];fibArray[0] 0;fibArray[1] 1;for (int i 2; i n ; i) {fibArray[i] fibArray[i - 1] fibArray [i - 2];}return fibArray;} 我们可以看到这次创建了临时空间方法进来之后才创建方法出去之后才销毁。下面除了i也没有创建额外的临时空间了所以上面代码的空间复杂度才是。
五、学习时间复杂度和空间复杂度的好处 学习时间复杂度目的是为了能够正确的使用数据结构。数据结构有很多种比如数组、队列、哈希表、栈、二叉树以及平衡树等这些数据结构在不同场景中会有不同的应用。要想知道那种数据结构更合适就要使用时间复杂度和空间复杂度来衡量。
