首页
精选文章冒泡排序查看全文冒泡排序是一种简单的朴素的排序算法，像自然界中很多冒泡现象一样，在气泡上升的过程中，会逐渐变大，所以气泡从下到上会呈现出从小到大基本有序的场景。冒泡排序每一轮会找出一个集合中的最大值，然后将该最大值放于集合的尾部。 当最大值的位置确定之后，下一轮会找出集合中剩余数据的次大值，然后放在上一轮最大值前面的位置。 以此类推，直到所有的值从从大到小都放在了正确的位置。 假如一个数据量为n的数据集，需要从小到大进行排序，冒泡排序需要循环n轮。 每一轮循环找出剩余元素中的最大值，然后放在未排序集合的最后位置，例如第一轮找出全局的最大值，放在第n-1位，那么最后一位是已经排好序的，下一轮找出剩余n-1个元素的最大值，之后放在第n-2的位置。以此类推。 每一轮找最大值的过程，也是一轮循环，从前到后，将当前的最大值和当前值比较，如果当前值比最大值大，则将当前值和最大值交互，这一轮循环的过程中，最大值始终位于已经比较过的集合的最后位置。计算机组成原理查看全文计算机一般分为几个部分：存储系统，计算系统以及输入输出设备。存储系统 对于存储器而言，分层概念非常重要，因为速度较快的存储往往价格比较昂贵，而且容量较小，而容量较大的存储虽然价格便宜，但是往往速度较慢。 基于上述原因，存储器一般分为高速缓存，主存以及辅存等层次。 高速缓存主要是解决CPU和主存之间速度不匹配的问题，通过大量典型程序分析发现CPU在从主存取指令或者数据时，在一定时间内只是对主存局部地址区域的访问，即指令和数据在主存的位置不是随机的而是相对的簇聚，使得CPU在访问时具有相对的局部性。也就是程序访问的局部性原理。所以CPU可以将主存的数据提前加载到高速缓存中，进行计算，可以有效提高CPU计算的吞吐速度。高速缓存虽然属于存储系统，但是一般集成在CPU内部。 辅存解决的是容量问题，Linux系统下的虚拟内存空间可以提供比物理内存大的多的内存空间。 运算器 ALU（算数逻辑单元）通常是指一个组合电路，使用寄存器保存参与计算的结果。 控制器 控制器的功能是解释并且执行指令。 PC，程序计数器寄存器保存了当前指令的地址，进行读取指令，PC有计数功能。 IR，指令寄存器存放了当前要执行的指令，将操作码放入CU进行分析。 CU，控制单元，发出控制信号，控制对应的部分进行指令执行。 输入输出系统 在计算机早期阶段：I/O设备较少，与主存交换信息都必须通过CPU。程序查询方式是由CPU通过程序不断查询IO设备是否已经做好准备，从而控制IO设备与主机交换信息。即只要CPU启动IO设备，便停止执行原有程序，转入执行查询程序，不断查询IO设备是否已经做好准备。若查得IO设备未准备就绪，就继续查询…时间复杂度查看全文时间复杂度是计算机科学对程序耗时的一种衡量手段，时间复杂度通用使用O符号来表示，其衡量纬度通常使用输入数据的长度，最终写成O(f(n))。数据复杂度中的大O用来表示算法时间复杂的渐近上界，因为对于同一个算法，在不同的输入情况下，计算的次数会存在较大的差异，例如插入排序，在数据有序的情况下其时间复杂度是O(n)，但是在数据无序的情况下，其时间复杂度是会O（n2），所以我们提到插入排序其时间复杂度是O（n2）。 快速排序在数据逆序的情况下时间复杂度是O（n2），但是平均情况下，快速排序的时间复杂度是O（n*log（n））。O表达的近似复杂度一般情况描述的更加偏向一般情况下的时间复杂度，而不是严格的上界。 除了O之外，还有下列符号也是描述时间复杂度的符号； Θ，表示准确的时间复杂度，即时间复杂度的上界下界(tight) ο，表示算法复杂度的上界(not tight)，例如快速排序的上界时间复杂度是o（n2）。 Ω，表示渐进下界，该复杂度是最优情况下的近似复杂度。 ω，表示下界，表示最优情况下严格的时间复杂度。 常用的时间复杂度有O（n3）、O（n2）、O（n*log（n））。 时间复杂度在计算过程中，去忽略常数项系数，该常数项系数是指所有低于最高阶项的计算因子。 常见的计算项的阶度高低如下： O（2n）> O（n3）> O（n2）> O（n*log（n））> O（n）> O（log（n））> O（1） |
热门分类开源Golang消息队列JavaJavascriptLinuxMysqlNLPPHP事务内存管理分布式理论分类存储常用存储开源软件操作系统画图网络编程数据库算法虚拟化前端存储理论常用算法微服务数据结构算法应用计算机原理中间件共识算法分布式分治动态规划容器并发排序架构组件绘图工具网络协议编程语言理论算法思想树缓存架构C++字符串算法工程思想搜索
算法题库
精选内容 |
