[SoWhat ACM]0.I’m faster than you (时间复杂度 Time Complexity of Algorithms)


2015.11.22于SoWhat ACM QQ群

神犇说世上的美有三种,一是优美精致的数据结构,二是巧夺天工的神奇算法,三是你温暖世界的笑容

计算机之所以叫做计算机,就是因为它在“计算”这一件事上做的可以比人类快。而我们的任务,就是告诉计算机要如何去进行一个计算,也就是要实现一个算法。
想要让程序更快,除了要提升计算机处理器的运行速度之外,最重要的就是要提升算法的效率,以及算法的在这个计算机上实现的的速度。
做同样的一件事情,可以有无数种做法。比如说给一些数字排序,就有好几种做法。那么要怎么比较他们的速度呢?
最直观的做法自然是写出对应的程序,给定一个输入,然后比较一下他们的运行时间。这样的做法简单粗暴,然而并不能给我们关于这些算法的更多信息,也只能反映这些算法在这个特定输入的情况,误差也不容小视。
更为严谨的做法,是对这个算法进行数学上的分析,以得出这个算法在理论上的运行效率。
以选择排序为栗子把
(然后把栗子剥开吃掉~

来看看他的运行原理
选择排序
第零轮从所有的n个数据中找出最小的,需要对每个\(j\in \left ( 0,n \right )\)进行一次比较,共n-1次
第一轮从剩下的n-1个数据中找出最小的,需要对\(j\in \left ( 1,n \right )\)每个进行一次比较,共n-2次
……
第i轮从剩下的n-i个数据中找出最小的,需要对\(j\in \left ( i,n \right )\)每个进行一次比较,共n-i-1次
第n-2轮从剩下的2个数据中找出最小的,需要进行一次比较

总共需要进行 \(\sum_{k = 1}^{n-1} k=\frac{n\left ( n-1 \right )}{2}\)次比较
然后每轮需要对数据进行一次交换,合计是\(\left ( n-1 \right )\)次交换
也就是说,这个程序所需要运行的时间大致上是
\(T=\frac{n\left ( n-1 \right )}{2}T_{0}+\left ( n-1 \right )T_{1}\),其中\(T_{0}\)为一次比较需要的时间,\(T_{1}\)为一次交换所需要的时间
当n很大的时候,对T的量级起到决定性作用的将会是什么呢?
(还记得函数在无穷大的极限吗?
n趋向于无穷大时,起作用的将会是n的二次项,也就是\(\frac{n^{2}}{2}T_{0}\)
那么可以看出,选择排序的算法的运行时间在n充分大的时候,大致正比于\(n^{2}\)
继续阅读 “[SoWhat ACM]0.I’m faster than you (时间复杂度 Time Complexity of Algorithms)” »

[海韵日常]以及图集


军训结束,开学了。
说好的昨天写的,可是时间关系拖到了今天。
今天早上班级一起做了素质拓展活动,感觉萌萌哒。
以及下午参观了图书馆总部。回来后我在宿舍东图随手借了几本。
)剩下的明天写吧
继续阅读 “[海韵日常]以及图集” »

……其实只是想给这几天啥都没干找个借口而已嘛

Win10

GTA GTC15前就看到10240出来,抱着尝鲜的心态下了偷跑的ISO刻了个U盘,备份一下就从Win8.1U1Home升级到了Win10Pro……额果然没办法激活,先KMS撑了几天。

回来后就听说Win10开始推送了,想一想KMS续命可麻烦了……老老实实OTA

还原8.1,联想一键备份duang的一下告诉我“不能访问文件”……呵呵你把我C盘格了再告诉我没法还原?

神奇的是一个NTFS分区被格居然搞的我的Ubuntu都起不来了,我望着我电脑上唯一能用的系统——android5.1在月光下凌乱。

用U盘全新安装了个Win10Home,还是没法激活,先将就用着

折腾了半天备份文件确认是C盘的备份文件在备份时就损坏了,还原前赶时间没有备份Win10呵呵C盘所有数据都丢了吧

想一想有一个原厂Win8镜像恢复上,然后再安装Win10Home……嗯还是没办法激活。孩子激活老不好,多半是SKU废了

找了个OEM的镜像果然可以哈哈哈哈

然后我的GRUB呢?
继续阅读 “[Dr.Lib]工欲善其事,必先利其器” »

[时间线]一个莫名《奇妙的朋友》引发的公开博弈

via http://www.guokr.com/post/671772/

不要说什么只是看看节目而已又不会去伤害动物,对这种节目,放任就是对整个世界的伤害。 ——Librazy

 

 

2015年1月24日,湖南电视台开播了一档新的真人秀节目《奇妙的朋友》,主打的卖点是明星与动物园圈养的动物“亲密接触”。由此,引发了一场关于利益与良知的血战。

早在开播之前,根据《奇妙的朋友》节目组的前期宣传,@亚洲动物基金 就已经提出了质疑。2015年1月15日,他们在我们都在动物园小组发表了帖子:奇妙的朋友,还是远观吧,针对宣传照中人与动物(尤其是与大象)的“亲密接触”提出了质疑。 继续阅读 “[时间线]一个莫名《奇妙的朋友》引发的公开博弈” »

Windows 10 vs Longhorn

习惯了Start Screen和Charm Bar,现在在WindowsXP上关机都不会关了。想想不久以前还在迷恋Windows7酷炫的Aero、为了Mac的壁纸把Windows 7彻底搞成Mac的样子以及成功的在Windows上玩了一把桌面立方体……LOL,现在还不是Modern UI的支持者。

 

想起来家里买的台式机,大概就是Vista出来后第二年,标配Vista,貌似有Aero……之所以说貌似是因为抱回家的时候就变成蓝天白云一片绿了。现在想想刷回XP还是挺正确的。

XP诞生之时,正好是桌面系统飞速发展的时候,各家各户都用上了电脑。中国电脑桌面系统的标配,从DOS+WPS到了XP+OFFICE。开发软件的越来越多,打包盗版系统的也越来越多,玩游戏的也越来越多……就这样,XP在中国乃至世界的PC上站稳了脚跟。有一台装着XP的电脑,握着一台诺基亚就算是紧跟潮流了。

 

微软也没闲着,时代总要进步嘛,他们也在继续研发,Longhorn,Longhorn Reset,Vista。好吧这是退步了。

继续阅读 “Windows 10 vs Longhorn” »

[Dream YOLO]竞赛季的竞赛祭

首先9月10日就是教师节了,也在此恭喜各位老师事业顺利。

上半学期的8~11月,是各大竞赛集中举行的时间,也意味着这是竞赛党的冲刺阶段。作为一个退役的OIer,现役的CPHOer,我的感触也是蛮深的。二中14届为我们树立了一个高大上的目标,而我们这一届,也有许多人正在为了自己的目标而奋斗。

虽然,过程会有点曲折。

这几天老师安排了一些同学部分停课参加竞赛,按照同学自己的意愿选择每节课在班级上课或者是在实验室自习备考。很多同学也很羡慕那些竞赛小组的同学,可以不用开学考,可以不交作业,可以以各种理由跷课……

但不可避免的,这样子会影响到周边的其他同学,一定程度上影响了周边同学的学习,所以现在的选择变成了明确的二分:请假全天停课或者全天正常上课。

全天停课,也就是不需要跟从正常的进度,不需要做作业。但又会落下很多功课,影响成绩。本来就不到三百天的时间里再扣掉十几天不读书,影响看起来确实很大。再加上现在竞赛也没有保送也没有加分,何苦去浪费这十几天呢?

正常上课,在备考竞赛的基础上还要完成所有正常科目的作业,时间就更紧了,最坏的情况就是两边都遭到了损失却又没有什么效果。

单科的竞赛会牵涉到竞赛小组的很多成员和周边的同学,进而影响到其他科目的教学,从作业质量到课堂效率。

——竞赛,有多艰难?

竞赛生要付出的努力,比其他同学想象的要多的多。当别人在课间休息时,生竞党还在解决一道选择题。当别人在操场上打篮球时,物竞党还在刷某届的复赛题。当别人早已睡下,OIer还在通宵打CF(Codeforces。我昨天整理了一下房间,整理出信息学竞赛相关的书堆起来有750px高,但比很多真正的大神的书堆矮了一半。竞赛并不是与普通上课一样,跟随老师的节奏就可以做好的,而是需要大量的时间和精力去准备的。竞赛占用了这么多的时间,也不可避免的会影响到其他科目的学习,鱼与熊掌不可兼得嘛。

竞赛的竞争比一般的考试强烈的多,也严酷的多。全省几万人的预赛,只为了几十个的一等奖,注定绝大多数的人会作为炮灰。虽然我认同罗老师说的“过程是好的,那结果也会是好的。”,但竞赛并不是百分之几的努力再加百分之几的人品,而甚至更像努力乘以人品,变数极大。

竞赛已经没有了保送和加分,自招的Buff也是很小的,就算竞赛获了奖,也是很难有实际、直接的优势的。

——那为什么依然有那么多人选择竞赛?

曾经也和吴健老师聊到相关的话题,我以为竞赛取消保送和加分后人数会少很多,结果人数不减反增。没有了加分的竞赛,又有什么意义呢?就像我上面列的几点,选择竞赛本身压力和困难就很大。那竞赛可以给我们什么呢?

竞赛作为一种高强度的学习,本身就可以锻炼我们的知识储备和知识面。竞赛和正常上课很大的不同在于,老师在教学中占的比例更低了:师傅领进门,修行靠个人。竞赛可以很大程度上锻炼我们的自学能力、找到适合的学习方法。

竞赛也不是什么好学生的特权,只要你有兴趣,有想法,都可以参与,去尝试。竞赛成绩好坏和平时学习并没有什么必然的关系。

以及,从根本上来说,竞赛靠的是自己的兴趣和梦想,自己选择的奋斗目标。去掉了功利的保送与加分,竞赛最大的收获还是竞赛过程本身。凭借你的兴趣,才有可能认真的钻研竞赛的奥妙。无论结果如何,只要你喜欢,竞赛的过程其实总是充满乐趣的。每一道题、每一个知识点对你来说都是收获。去追寻自己在竞赛中近在咫尺的梦想。

附送两个来自NOI WC2014的节目

http://tieba.baidu.com/p/2883322463

http://tieba.baidu.com/p/2871105185

认真看完这两个节目,你就会明白竞赛的真正意义。

竞赛党也需要老师和同学们以及家长的鼓励、帮助和理解。竞赛过程中不可避免的会落下很多东西,但对于有经过竞赛锻炼的我们来说,这些都是很容易补上的。而竞赛,将是一分无法复制的收获。

无论选择安静的学习,还是选择充满挑战的竞赛,其实只有自己喜欢的路,才能走的最稳最好。

用一句来自某IOI#1的陈立杰引用过的话做结尾:自己选择的路,就算跪着也要走完。

 

 

… : ” ..\ 只要能够为了当时纯粹的梦想和感动坚持努力下去,不管其它人怎么样,我们也能够保持自己的本色走下去 /.. ” ….