ITPUB论坛-中国最专业的IT技术社区

 找回密码
 注册
查看: 10491|回复: 19

【大话IT】分析有趣算法背后的计算原理,从时间复杂度说起。。。

[复制链接]
论坛徽章:
8
2015年新春福章
日期:2015-04-22 09:15:50美羊羊
日期:2015-04-28 08:58:41暖羊羊
日期:2015-05-05 11:13:16慢羊羊
日期:2015-07-03 14:57:082017金鸡报晓
日期:2017-01-10 15:25:58目光如炬
日期:2016-06-05 22:00:00秀才
日期:2017-04-06 18:09:28秀才
日期:2017-05-09 11:37:55
发表于 2017-6-20 14:20 | 显示全部楼层 |阅读模式
本期获奖的童鞋有: 〇〇   owen_zeng   陌路巨额投入   jieforest   nail78   
请以上5位获奖人员在8月30日前将姓名、电话、邮箱、公司、职务、快递地址站短给  yejia80550708 ,以便尽快给大家发放礼品。
本期讨论问题:

提到算法、计算原理,我们可能会想到一些基础的东西,比如:计算机补码运算背后的数学原理再比如,关于时间的负责度。
请罗列出你所了解的,一些有趣算法的计算原理,并举例说明。(选1个自己了解的算法原理即可)


以下,引用了关于时间复杂度的经典举例,来引出我们今天的这个话题:

不管你是计算机科班出身还是想有效解决最优化问题,如果想要用自己的知识解决实际问题,你都必须理解时间复杂度。

先从简单直观的 O(1) 和 O(n) 复杂度说起。O(1) 表示一次操作即可直接取得目标元素(比如字典或哈希表),O(n) 意味着先要检查 n 个元素来搜索目标,但是 O(log n) 是什么意思呢?

你第一次听说 O(log n) 时间复杂度可能是在学二分搜索算法的时候。二分搜索一定有某种行为使其时间复杂度为 log n。我们来看看是二分搜索是如何实现的。

因为在最好情况下二分搜索的时间复杂度是 O(1),最坏情况(平均情况)下 O(log n),我们直接来看最坏情况下的例子。已知有 16 个元素的有序数组。

具体例子说明见楼层一


活动时间:2017年6月20日—7月20日


活动奖励:
活动结束后,我们将选取5位讨论精彩的同学,送技术图书《伟大的计算原理 》。
原书名:Great Principles of Computing
作者: (美)彼得J.丹宁(Peter J. Denning)    (美)克雷格H.马特尔(Craig H. Martell)   
译者: 罗英伟
丛书名: 计算机科学丛书
出版社:机械工业出版社
ISBN:9787111567264
上架时间:2017-5-10
出版日期:2017 年5月
开本:16开
版次:1-1

购书链接:http://product.china-pub.com/5738048

内容简介:本书系统总结了从算法到系统横跨整个计算机领域的6类计算原理(计算、通信、协作、记忆、评估和设计),旨在构建起一个框架帮助读者认识计算思维,领会其核心思想──计算原理的相互影响以及问题有效解决的思维方式,并将计算思维运用到计算机科学以外的其他领域。

样章试读: 1-3z.pdf (6.76 MB, 下载次数: 31)
论坛徽章:
8
2015年新春福章
日期:2015-04-22 09:15:50美羊羊
日期:2015-04-28 08:58:41暖羊羊
日期:2015-05-05 11:13:16慢羊羊
日期:2015-07-03 14:57:082017金鸡报晓
日期:2017-01-10 15:25:58目光如炬
日期:2016-06-05 22:00:00秀才
日期:2017-04-06 18:09:28秀才
日期:2017-05-09 11:37:55
 楼主| 发表于 2017-6-20 14:26 | 显示全部楼层
举个最坏情况的例子,比如我们要找的是数字 13。
伟大的计算原理 活动819.png
十六个元素的有序数组
伟大的计算原理 活动1245.png
选中间的元素作为中心点(长度的一半)
伟大的计算原理 活动1679.png
13 小于中心点,所以不用考虑数组的后一半
伟大的计算原理 活动2116.png
重复这个过程,每次都寻找子数组的中间元素
伟大的计算原理 活动2552.png
伟大的计算原理 活动2967.png

每次和中间元素比较都会使搜索范围减半。
所以为了从 16 个元素中找到目标元素,我们需要把数组平均分割 4 次,也就是说,
伟大的计算原理 活动3442.png
简化后的公式
类似的,如果有 n 个元素,
伟大的计算原理 活动3877.png
归纳一下
伟大的计算原理 活动4295.png
分子和分母代入指数
伟大的计算原理 活动4718.png
等式两边同时乘以 2^k
伟大的计算原理 活动5144.png
最终结果
现在来看看「对数」的定义:
为使某数(底数)等于一给定数而必须取的乘幂的幂指数。
也就是说可以写成这种形式
伟大的计算原理 活动5616.png
对数形式
所以 log n 的确是有意义的,不是吗?没有其他什么可以表示这种行为。

使用道具 举报

回复
论坛徽章:
146
知识
日期:2015-06-25 13:49:18秀才
日期:2015-09-06 10:19:32双鱼座
日期:2015-09-06 10:26:43秀才
日期:2015-09-06 10:32:56秀才
日期:2015-09-06 10:42:32白羊座
日期:2015-10-31 09:07:11秀才
日期:2015-09-10 09:29:01秀才
日期:2015-09-14 10:08:30秀才
日期:2016-02-18 09:11:33秀才
日期:2015-09-21 09:46:16
发表于 2017-6-20 15:06 | 显示全部楼层
二分法的搜索复杂度是 O(log n)

使用道具 举报

回复
认证徽章
论坛徽章:
210
状元
日期:2015-08-13 09:42:33榜眼
日期:2015-08-03 13:57:54探花
日期:2015-07-31 13:44:02举人
日期:2015-07-01 15:00:51进士
日期:2015-07-27 11:26:49秀才
日期:2015-07-27 09:45:522015年中国系统架构师大会纪念徽章
日期:2015-07-23 09:58:092014系统架构师大会纪念章
日期:2015-07-23 09:58:092013系统架构师大会纪念章
日期:2015-07-23 09:58:092012系统架构师大会纪念章
日期:2015-07-23 09:58:09
发表于 2017-6-20 15:31 | 显示全部楼层
好高深啊。呵呵。不理解。

使用道具 举报

回复
认证徽章
论坛徽章:
3
慢羊羊
日期:2015-03-04 14:51:352015年新春福章
日期:2015-03-06 11:57:31秀才
日期:2017-08-18 11:02:47
发表于 2017-6-20 17:04 | 显示全部楼层
得好好把数学都捡起来

使用道具 举报

回复
论坛徽章:
8
2015年新春福章
日期:2015-04-22 09:15:50美羊羊
日期:2015-04-28 08:58:41暖羊羊
日期:2015-05-05 11:13:16慢羊羊
日期:2015-07-03 14:57:082017金鸡报晓
日期:2017-01-10 15:25:58目光如炬
日期:2016-06-05 22:00:00秀才
日期:2017-04-06 18:09:28秀才
日期:2017-05-09 11:37:55
 楼主| 发表于 2017-6-20 17:17 | 显示全部楼层
guoleopard 发表于 2017-6-20 17:04
得好好把数学都捡起来

计算原理懂一些,代码估计会写的更规整,这是我个人的理解

使用道具 举报

回复
论坛徽章:
394
阿斯顿马丁
日期:2014-01-03 13:53:522014年世界杯参赛球队:喀麦隆
日期:2014-07-11 12:10:53马上有对象
日期:2014-04-09 16:19:542014年世界杯参赛球队: 洪都拉斯
日期:2014-06-25 08:25:55itpub13周年纪念徽章
日期:2014-09-28 10:55:55itpub13周年纪念徽章
日期:2014-10-01 15:27:22itpub13周年纪念徽章
日期:2014-10-09 12:04:18马上有钱
日期:2014-10-14 21:37:37马上有钱
日期:2015-01-22 00:39:13喜羊羊
日期:2015-02-20 22:26:07
发表于 2017-6-21 20:07 | 显示全部楼层
求200!的不同因数个数
穷举法是不行的
而利用勒让德定理,可知n!的质因数p的指数pe是∑(n/p^i)
然后求∏(pe+1)就行了

使用道具 举报

回复
认证徽章
论坛徽章:
9
慢羊羊
日期:2015-03-04 14:55:272015年新春福章
日期:2015-03-06 11:59:47技术图书徽章
日期:2017-02-09 17:05:19秀才
日期:2017-02-22 15:16:26秀才
日期:2017-02-22 15:18:00现任管理团队成员
日期:2017-06-03 02:10:11版主1段
日期:2017-06-05 09:06:08秀才
日期:2017-08-18 11:04:35秀才
日期:2017-09-18 17:02:49
发表于 2017-6-26 14:52 | 显示全部楼层
王楠w_n 发表于 2017-6-20 14:26
举个最坏情况的例子,比如我们要找的是数字 13。
十六个元素的有序数组选中间的元素作为中心点(长度的一 ...

写得非常好,不过中间好像多了一步。分子和分母代入指数

这个是不需要的,前面一步直接2边都乘以 2^k 就可以。另外咨询一个问题O (log n) 这里的底数是2. 这个2对不同算法,值是不同的吗?

使用道具 举报

回复
论坛徽章:
7
秀才
日期:2016-02-18 09:39:10秀才
日期:2016-02-18 10:08:14秀才
日期:2017-03-01 13:53:39秀才
日期:2017-04-06 18:09:28秀才
日期:2017-08-18 11:02:47秀才
日期:2017-08-18 11:04:35秀才
日期:2017-09-18 17:02:05
发表于 2017-6-27 18:36 | 显示全部楼层
好久没研究这东西了 - -0

使用道具 举报

回复
论坛徽章:
9
秀才
日期:2017-06-29 10:10:37秀才
日期:2017-06-29 10:16:48技术图书徽章
日期:2017-06-29 10:17:04秀才
日期:2017-06-29 10:17:04秀才
日期:2017-08-11 15:37:01秀才
日期:2017-08-11 15:37:01秀才
日期:2017-08-11 15:37:01秀才
日期:2017-08-11 15:37:01秀才
日期:2017-08-23 14:11:07
发表于 2017-6-30 09:47 | 显示全部楼层
支持一下!

使用道具 举报

回复

您需要登录后才可以回帖 登录 | 注册

本版积分规则

SACC2017购票8.8折优惠进行时

2017中国系统架构师大会(SACC2017)将于10月19-21日在北京新云南皇冠假日酒店震撼来袭。今年,大会以“云智未来”为主题,云集国内外顶级专家,围绕云计算、人工智能、大数据、移动互联网、产业应用等热点领域展开技术探讨与交流。本届大会共设置2大主会场,18个技术专场;邀请来自互联网、金融、制造业、电商等多个领域,100余位技术专家及行业领袖来分享他们的经验;并将吸引4000+人次的系统运维、架构师及IT决策人士参会,为他们提供最具价值的交流平台。
----------------------------------------
优惠时间:2017年8月30日前

活动链接>>
TOP技术积分榜 社区积分榜 徽章 电子杂志 团队 统计 虎吧 老博客 知识索引树 读书频道 积分竞拍 文本模式 帮助
  ITPUB首页 | ITPUB论坛 | 数据库技术 | 企业信息化 | 开发技术 | 微软技术 | 软件工程与项目管理 | IBM技术园地 | 行业纵向讨论 | IT招聘 | IT文档 | IT博客
  ChinaUnix | ChinaUnix博客 | ChinaUnix论坛 | SAP ERP系统
CopyRight 1999-2011 itpub.net All Right Reserved. 北京盛拓优讯信息技术有限公司版权所有 联系我们 网站律师 隐私政策 知识产权声明
京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802021510 广播电视节目制作经营许可证:编号(京)字第1149号
  
快速回复 返回顶部 返回列表