投稿    登录
欢迎来访~

重学算法与探究

Python Payne 1086浏览 0评论

扫码或搜索:进击的Coder

发送

即可立即永久解锁本站全部文章

写在最前面:本人也是个算法小白,如果有什么不对还望大佬指正,谢谢

算法设计评价基本标准

算法是对特定问题求解步骤的一种描述,如果将问题看作函数,那么算法是吧输入转化为输出

算法:

是对特定问题求解步骤的一种描述,是为了解决一个或者一类问题给出的 一个确定的、有限长的操作序列。

算法的设计依赖于数据的存储结构,因此对确定的问题,应该需求子啊适宜的存储结构上设计出一种效率较高的算法

算法的重要特性:

有穷性:

对于任何一组合法的输入值,在执行有穷步骤之后一定能结束,即算法中的操作步骤为有限个,并且每个步骤都能在有限的时间内完成

确定性:

对于每种情况下所应该执行的路径的操作,在算法中都有确切的规定,使算法的执行者或阅读者都能明确其含义及如何执行;并且在确切的条件下只有唯一一条执行流程路径

可行性:

算法中的所有操作都必须足够基本,都可以通过已经实现的基本运算执行有限次实现

有输入:

作为算法加工对象的量值,通常体现为算法中的一组变量。有些输入量需要在算法的执行过程中输入,而有些算法表面上没有输入,但实际上已被嵌入算法之中

有输出:

它是一组与“输入”有确定关系的量值,是算法进行信息加工够得到的结果。这种确定关系即为算法的功能

算法设计目标:

正确性:

算法应满足具体问题的需求,正确反映求解问题对输入、输出加工处理等方面的需求

  1. 程序中不含语法错误,计算的结果却不能满足规格说明要求。
  2. 程序对于特定的几组输入数据能够得出满足要求的结果,而对于其他的输入数据的不出正确的计算结果;
  3. 程序对于精心选择的、经典、苛刻且带有刁难性的几组输入数据能够得到满足需求的结果;(正确的算法)
  4. 程序对于一切合法的输入数据都能得出满足要求的结果

可读性:

算法处理用于编写程序子啊计算机上执行之外,另一个重要用处是阅读和交流。

算法中加入适当的注释,介绍算法的设计思路、各个模块的功能等一些必要性的说明文字来帮助读者理解算法。

要求:

算法中加入适当的注释,介绍算法的设计思路、各个模块的功能等一些必要性的说明文字来帮助读者理解算法

对算法中出现的各种自定义变量和类型能做到“见名知义”,即读者一看到某个变量(或类型名)就能知道其功能

健壮性:

当输入数据非法时,算法能够适当地做出反应或进行处理,输出表示错误性质的信息并终止执行,而不会产生莫名其妙的输出结果。

时间效率与存储占用量:

一般来说,求解同一个问题若有多种算法,则

执行时间短的算法效率高

占用存储空间少的算法较好

算法的执行时间开销和存储空间开销往往相互制约,对高时间效率和低存储占用的要求只能根据问题的性质折中处理

算法复杂度

算法的时间复杂度:

算法的效率指的是算法的执行时间随问题“规模”(通常用整型量n表示)的增长而增长的趋势

“规模”在此指的是输入量的数目,比如在排序问题中,问题的规模可以是被排序的元素数目

假如随着问题规模n的增长,算法执行时间的增长率和问题规模的增长率相同则可记为:

T(n) = O(f(n))

f(n) 为问题规模n的某个函数;

T(n)被称为算法的(渐进)时间复杂度(Time Complexity)

O表示法不需要给出运行时间的精确值;

选择f(n),通常选择比较简单的函数形式,并忽略低次项和系数

常用的有O(1)、O(logn)、O(n)、O(nlogn)、O(n*n)等等

多项式时间复杂度的关系为:

O(1) < O(logn) < O(n) < O(N logn) < O(n²) < O(n³)

指数时间算法的关系为:

O(2(n方))< O(n!) <O(n(n方))

由于估算算法时间复杂度关心的只是算法执行时间的增长率而不是绝对时间,因此可以忽略一些因素。

方法:从算法中选取一种对于所研究的问题来说是“基本操作”的原操作,以该“基本操作”在算法中重复执行的次数作为算法时间复杂度的依据。

EG:

两个n x n 的矩阵相乘,求其时间复杂度

问题规模是矩阵的阶n,算法的控制结构式三重循环,基本操作是乘法操作

乘法执行次数为n³,则算法的时间复杂度为O(n³)

算法的空间复杂度:

算法在执行期间所需要的存储量包括:

  1. 程序代码所占用空间
  2. 输入数据所占用空间
  3. 辅助变量所占用的空间

为了降低复杂度,一个直观的思路是:梳理程序,看其流程中是否有无效的计算或者无效的存储。我们需要从时间复杂度和空间复杂度两个维度来考虑。

常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划等,

降低空间复杂度的方法,就要围绕数据结构做文章了。

降低空间复杂度的核心思路就是,能用低复杂度的数据结构能解决问题,就千万不要用高复杂度的数据结构。

如何评定一个程序算法的好坏?

简而言之:在符合算法设计标准的前提下,运行的更快、所用计算资源更少。即是更好的算法

请注意这里的比较级别词!!!,对于算法,个人认为就是获得同一结果的同时探究最优解决之道

探究算法优化(自我一点点小体悟-个人能力有限)
  1. 抽象化:将不必要的计算过程去掉

    利用高斯算法解决累计求和问题

  2. 慎选各数据结构,善用第三方算法

    去重:

    善用迭代什么的等等

    使用字典的特性-不可重复性

    布隆过滤器去重(源于哈希算法)

  3. 时空转换:将昂贵的时间转化为廉价的空间

    当‘优无可优时’,取贵舍廉

    空间是可以用买的,加个什么内存啊,加个处理器等等什么的

    时间是逝去就不在了

    以上仅仅个人的一点点小灵感,望大家不喜勿喷

说了这么多,来道简单的算法题目导入(同一计算机,i5, python)

需求如下:累计求和1-n的值(1. 为防止误差,验证10次; 2. 验证每次计算次数)

Sum is 100010000 Required 0.0010061264 seconds count = 10001
Sum is 100010000 Required 0.0009891987 seconds count = 10001
Sum is 100010000 Required 0.0000000000 seconds count = 10001
Sum is 100010000 Required 0.0010235310 seconds count = 10001
Sum is 100010000 Required 0.0009710789 seconds count = 10001
Sum is 100010000 Required 0.0000000000 seconds count = 10001
Sum is 100010000 Required 0.0009973049 seconds count = 10001
Sum is 100010000 Required 0.0010013580 seconds count = 10001
Sum is 100010000 Required 0.0000000000 seconds count = 10001
Sum is 100010000 Required 0.0019786358 seconds count = 10001

探究可知:n扩大10倍,运算时间也会扩大10倍

高斯算法,从1累加至n,等于(首项+尾项)项数/2
直接引用结论:
1+2+3+…+(n-1) +n={(1+n)+(2+(n-1))…}/2 = (n
(n + 1))/2

计算结果如下:

循环计算10000次,出去I/O所需时间几乎可以不计。

Sum is 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 Required 0.0000000000000000000000000000000000000000000000000123123000000000000000000000000000000000000000000000 seconds count = 5000000000000000079514455548799590234180404281972640694890663778873919386085190530406734992928407552
Sum is 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 Required 0.000000000000000000000000000000000000000000000000012332100000000000000000000000000000000000000000000 seconds count = 5000000000000000079514455548799590234180404281972640694890663778873919386085190530406734992928407552
Sum is 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 Required 0.00000000000000000000000000000000000000000000000000000002310000000000000000000000000000000000000 seconds count = 5000000000000000079514455548799590234180404281972640694890663778873919386085190530406734992928407552
Sum is 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 Required 0.000000000000000000000000000000000000000000000000000000000000120000000000000000000000000000000000000000 seconds count = 5000000000000000079514455548799590234180404281972640694890663778873919386085190530406734992928407552
Sum is 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 Required 0.000000000000000000000000000000000000000000000000000000010032000000000000000000000000000000000000 seconds count = 5000000000000000079514455548799590234180404281972640694890663778873919386085190530406734992928407552
Sum is 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 Required 0.0000000000000000000000000000000000000000000000012231300000000000000000000000000000000000000000000 seconds count = 5000000000000000079514455548799590234180404281972640694890663778873919386085190530406734992928407552
Sum is 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 Required 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 seconds count = 5000000000000000079514455548799590234180404281972640694890663778873919386085190530406734992928407552
Sum is 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 Required 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 seconds count = 5000000000000000079514455548799590234180404281972640694890663778873919386085190530406734992928407552
Sum is 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 Required 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 seconds count = 5000000000000000079514455548799590234180404281972640694890663778873919386085190530406734992928407552
Sum is 49999999999999998486656110625518082973725163772751181324120875475173424217777037767098169202353125934013756207986941204091067867184139242319692520523619938935511795533394990905590906653083564427444224 Required 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 seconds count = 5000000000000000079514455548799590234180404281972640694890663778873919386085190530406734992928407552

 

转载请注明:静觅 » 重学算法与探究

更多文章、联系博主、技术交流、商务合作

扫码或搜索:进击的Coder

进击的Coder

微信公众号 扫一扫关注

喜欢 (12)or分享 (0)

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请狠狠点击下面的

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址