网站建设价格女,淄博网络宣传,辽宁省建设工程造价管理网站,房山建站公司目录
算法
评价标准
时间的复杂度
概念
推导原则
举例
空间的复杂度
定义
情形
运用场景
数据结构
组成方式 算法
在数学领域#xff0c;算法是解决某一类问题的公式和思想#xff1b;
计算机科学领域#xff0c;是指一系列程序指令#xff0c;用于解决特定的…目录
算法
评价标准
时间的复杂度
概念
推导原则
举例
空间的复杂度
定义
情形
运用场景
数据结构
组成方式 算法
在数学领域算法是解决某一类问题的公式和思想
计算机科学领域是指一系列程序指令用于解决特定的运算和逻辑问题
评价标准
衡量算法好坏的重要标准是时间复杂度和空间复杂度
代码运行时间的长短和占用内存空间的大小是衡量程序好坏的重要因素。
时间复杂度主要衡量的是一个算法的运行速度而空间复杂度主要衡量一个算法所需要的额外空间
时间的复杂度
概念 计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间
推导原则 如果运行时间是常数量级则用常数1表示 只保留时间函数中的最高阶项 如果最高阶项存在则省去最高阶项前面的系数
举例
例1给小灰1个长度为10cm的面包小灰每3分钟吃掉1cm那么吃掉整个面 包需要多久 答案是3×10即30分钟。 如果面包的长度是n cm呢 此时吃掉整个面包需要3乘以n即3n分钟。 如果用一个函数来表达吃掉整个面包所需要的时间可以记作T(n) 3nn为面 包的长度
例2给小灰1个长度为16cm的面包小灰每5分钟吃掉面包剩余长度的一半 即第5分钟吃掉8cm第10分钟吃掉4cm第15分钟吃掉2cm……那么小灰把面包吃得 只剩1cm需要多久呢 把面包吃得只剩下1cm需要5×log16即20分钟。 如果面包的长度是n cm呢 此时需要5乘以logn即5logn分钟记作T(n) 5logn。
设T(n)为程序基本操作执行次数的函数n为输入规模刚才的2个场景分别对应了程序中最常见的2种执行方式
例1中T(n) 3n执行次数是线性的最高阶项为3n省去系数3则转化的时间复杂度为T(n)O(n)。 例2中T(n) 5logn执行次数是用对数计算的最高阶项为5logn省去系数5则转化的时间复杂度为T(n) O(logn)。 渐进时间复杂度用大写O来表示所以也被称为大O表示法
空间的复杂度 在运行一段程序时我们不仅要执行各种运算指令同时也会根据需要存储 一些临时的中间数据以便后续指令可以更方便地继续执行。
定义 是对一个算法在运行过程中临时占用存储空间大小的量度空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。
情形
1.常量空间当算法的存储空间大小固定和输入规模没有直接的关系时空间复杂度记 作O(1)。
2.线性空间当算法分配的空间是一个线性的集合如数组并且集合大小和输入规模n成 正比时空间复杂度记作O(n)。
3.二维空间当算法分配的空间是一个二维数组集合并且集合的长度和宽度都与输入规模n 成正比时空间复杂度记作O(n 2 )。
4.递归空间递归是一个比较特殊的场景。虽然递归代码中并没有显式地声明变量或集合 但是计算机在执行程序时会专门分配一块内存用来存储“方法调用栈”。
运用场景 1.运算 2.查找 3.排序 4.最优决策
数据结构 是数据的组织、管理和存储格式其使用目的是为了高效的访问和修改数据
组成方式
1.线性结构最简单的数据结构其中包括了数组、链表、以及衍生出来的栈、队列、哈希表 2.树相对复杂的数据结构其中有代表性的是二叉树由它又衍生出二叉堆之类的数据结构 3.图是更为复杂的数据结构在图中会呈现出多对多的关联关系 4.其他数据结构由基本数据结构变形而来用于解决某些特定问题如跳表、哈希链表、位图 等
注意 有了数据结构算法才能尽情地发挥在解决问题时不同的算法会选用不同的数据结构
