Notifications
Article
算法初探
Published 2 months ago
663
3
认识基本算法
前言: 在数学领域里面,“算法”是用于解决某一类问题的公式和思想。 在计算机科学与技术领域里面,“算法”的本质是一系列程序指令,用于解决特定的运算和逻辑问题。
算法应用的领域: 1)运算 2)查找 3)排序 4)最优决策
算法有高效的,也有拙劣的,衡量算法的好坏重要标准是:时间复杂度和空间复杂度。 这两个名词来自“数据结构”(data structure),其中“数据结构"是算法的基石。 那什么是数据结构? 数据结构是数据的组织、管理和存储格式,其使用目的是为了高效地访问和修改数据。 通俗的说对数据结构的操作就是增、删、查、改4种情况。
一、时间复杂度和空间复杂度 代码的绝对执行时间是无法预估的,但我们却可以预估代码的基本操作执行次数。 1)时间复杂度 高中数学里面常见的一些函数,如: f(n) = 5 f(n) = 5n f(n) = 5logn f(n) = 5n^2 + 5n 官方定义: 若存在函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n) = O(f(n)),称为O(f(n)),O为算法的渐进时间复杂度,简称为时间复杂度。 简单理解就是,把相对执行时间函数f(n)简化为一个数量级,上面的函数对应的时间复杂度表示: O(1),O(n),O(logn),O(n^2) 当n取足够大时, O(1)<O(logn)<O(n)<O(n^2) 在编程的世界中有各种各样的算法,对应不同形式的时间复杂度,如O(nlogn), O(n^3) , O(n!)等,算法运行时间比较可参考: https://blog.csdn.net/x_panda/article/details/16974709 O(1)被称为常量时间,并不意味着马上,而是不管列表多大,所需的时间都相同. 算法中log级别的时间复杂度都是由于使用了分治思想,这个底数直接由分治的复杂度决定.你如果采用二分法,那么就会以2为底数,三分法就会以3为底数,其他亦然;从理论上,无论低是什么都无关紧要,因为不同底的logn之间只存在常数倍的关系,这与n无关,不会影响复杂度的大小。 2)空间复杂度 在运行一段程序时,不仅要执行各种运算指令,同时也会根据需要,存储一些临时的中间数据,以便后续指令可以更方便地继续执行。 eg:假如有n个整数,其中有两个整数是重复的,要求找出这两个重复的整数。 最直接是方式是双重循环,根据上面的概念,时间复杂度是O(n^2) 如果利用中间数据,遍历整个数列时,每遍历一个整数,就放到字典(散列表)中存起来,当遍历到下一个整数时,直接去字典(散列表)中查找,看有没有对应的即可。由于字典本身的时间复杂度是O(1),所以整个算法的时间复杂度是O(n) 第二种方式虽然减少了时间,但是增加了内存占用,那么描述一个算法占用的内存空间大小的重要指标就是——空间复杂度。 常见的空间复杂度: <1> 常量空间 int var = 5; <2> 线性空间 int[] array = new int[n] <3> 二维空间 int[][] matrix = new int[n][n] <4> 递归空间 递归代码中并没有显示地声明变量或集合,但是计算机在执行程序时,会专门分配一块内存,用来存储”方法调用栈“。 当进入一个新方法时,执行入栈操作,把调用的方法和参数信息压入栈中。 当方法返回时,执行出栈操作,把调用的方法和参数信息从栈中弹出。 纯粹的递归操作的空间复杂度也是线性的,因此递归深度是n的话,那空间复杂度就是O(n) 3)时间与空间的取舍 我们常听到”牺牲时间换空间“,或“空间换时间”这类描述,正如前面举的例子就是牺牲空间换时间,在绝大多数时候,时间复杂度更为重要一些,宁可多分配一些内存空间,也要提升程序的执行速度。
二、数据结构基础 数据结构分为物理结构和逻辑结构:
(1)数组(array) 特点:在内存中顺序存储,每一个元素都存储在小小的内存单元中,并且紧密排列,既不能打乱元素的存储顺序,也不能跳过某个存储单元进行存储。 数组的读取元素和更新元素可以直接根据下标读取元素,因此时间复杂度为O(1) 数组的插入元素和删除元素需要涉及元素的移动,因此时间复杂度为O(1) 数组的优势和劣势: 数组拥有非常高效的随机访问能力,可以用常量时间找到对应元素。有一种高效的查找算法叫二分查找,就是利用了数组的这个优势。 数组的插入和删除会导致大量元素被迫移动,影响效率。 总的来说,数组适合读操作多,写操作少的场景。而链表恰恰相反。 (2)链表(linked list) 特点:链表在内存中的存储方式是随机存储。 链表的每一个节点分布在内存的不同位置,依靠next指针关联起来。可以灵活有效地利用零散的碎片空间。 链表查找元素时,不像数组那样可以通过下标快速进行定位,只能从头节点开始向后一个一个节点逐一查找。因此最坏的时间复杂度为O(n) 链表的插入(头部,中间,尾部)的时间复杂度为O(1),只要内存允许,可以一直插入元素,不需要像数组那样考虑扩容问题。 链表的删除的时候复杂度也为O(1),许多高级语言,如C#,拥有垃圾回收机制,所以不用刻意去释放被删除的节点,只要外部没有引用,被删除的节点会被自动清理掉。
散列表(也叫哈希表hash table) 这种数据结构提供了键(key)和值(value)的映射关系,只要给出一个key,就可以高效查找到它所匹配的value,时间复杂度接近于O(1) 基本原理 散列表本质上也是一个数组,可是数组只能根据下标,如a[0],a[1],a[2]这样来访问,而散列表的key以字符串类型为主,那么是如何访问到数据的呢? 其实是通过哈希函数,把key和数组下标进行转换;这个哈希函数类似于“中转站”。 在大多数面向对象的语言中,每一个对象都有属于自己的hashcode,这个hashcode是区分不同对象的重要标识。无论对象自身的类型是什么,它们的hashcode都是一个整形变量。 转化方式 index = HashCode(key)%Array.Length 1)插入 在散列表里插入新的键值对(“name”,“Milk”),首先会通过哈希函数把key转换为数组的下标index,如果数组下标index对应的位置没有元素,那么就把这个值填充到下标index的位置。 由于数组的长度是有限的,当插入的元素越来越多时,不同的key通过哈希函数获得的下标可能是相同的,造成了哈希冲突 有种解决方式是“外部拉链法”,主要思想是基于数组和链表的组合来解决冲突。 hashMap数组的每一个元素不仅是一个数据对象,还是一个链表的头节点,每一个数据对象通过next指针指向它的下一个数据节点。当新来的数据映射到与之冲突的数组位置时,只需要插入到对应的链表中。
散列表是基于数组实现的,那么也会涉及扩容的问题。 当多次插入元素,散列表达到一定饱和度时,key映射位置发生冲突的概率会逐渐提高,那么大量元素拥挤在相同数组下标位置,形成很长的链表。对插入和查询的的性能都会影响。 loadFactor加载因子是表示Hsah表中元素的填满的程度. 加载因子越大,填满的元素越多,好处是,空间利用率高了,但冲突的机会加大了。链表长度会越来越长,查找效率降低。 反之加载因子越小,填满的元素越少,冲突的机会减小了,但空间浪费多了。表中的数据将过于稀疏(很多空间还没用,就开始扩容了) 因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡,默认值为0.75f 临界值 = 加载因子*容量 (当实际大小超过临界值时,会进行扩容) 2)读取 给定的key,通过哈希函数把key转化成数组下标,找到对应下标的所有元素,由于数组的每一个元素都与一个链表对应,可以顺着链表往下找,找到与key相匹配的节点。 数组和链表都被直接映射到内存,但散列表更复杂,它使用散列表函数来确定元素的存储位置。 散列表也使用数组来存储数据,因此其获取元素的速度与数组一样快。
Tags:
Ritern
Programmer
6
Comments
Ritern
a month ago
杨富数组的插入元素和删除元素、时间复杂度为O(1)还是O(n)?我记得是O(n)呀
无序数组的插入是一个与数组中的数据项个数无关的算法,新数据项总是被放在一个"空"的地方,插入的时间是一个常数
0
杨富
2 months ago
数组的插入元素和删除元素、时间复杂度为O(1)还是O(n)?我记得是O(n)呀
0
NuoXu
2 months ago
博主讲的很细致啊,受益匪浅,我学到了很多以前没注意到的点
0