苏州微信公众号开发【苏州网络推广】苏州建站、苏州网站维护、苏州网页制作、苏州微信小程序代运营公司

发表日期： 2021-04-24 09:05:26 浏览次数：148

苏州，简称“苏”，古称姑苏、平江，是江苏省地级市，国务院批复确定的中国长江三角洲重要的中心城市之一、国家高新技术产业基地和风景旅游城市 [1] 。截至2019年，全市下辖5个区、代管4个县级市，总面积8657.32平方千米，建成区面积477.63平方千米，常住人口1075万人，城镇人口827.7万人，城镇化率77%。 [2-3]

苏州地处中国华东地区、江苏东南部、长三角中部，是扬子江城市群重要组成部分，东临上海、南接嘉兴、西抱太湖、北依长江，地处东经119°55′～121°20′，北纬30°47′～32°02′之间。全市地势低平，平原占总面积的54.8%，海拔4米左右，丘陵占总面积的2.7%。苏州属亚热带季风海洋性气候，四季分明，雨量充沛，种植水稻、小麦、油菜，出产棉花、蚕桑、林果，特产有碧螺春茶叶、长江刀鱼、太湖银鱼、阳澄湖大闸蟹等。 [4-5]

苏州是首批国家历史文化名城之一，有近2500年历史，是吴文化的重要发祥地，有“人间天堂”的美誉。中国私家园林的代表——苏州古典园林和中国大运河苏州段被联合国教科文组织列为世界文化遗产。 [6-7]

2020年6月，经中央依法治国委入选为第一批全国法治政府建设示范地区和项目名单。

No. 0-2　运行时间的计算方法

了解输入数据的量和运行时间之间的关系

上一节在结尾说明了算法的不同会导致其运行时间产生大幅变化，本节将讲解如何求得算法的运行时间。

使用相同的算法，输入数据的量不同，运行时间也会不同。比如，对 10 个数字排序和对 1 000 000 个数字排序，大家很容易就想到后者的运行时间更长。那么，实际上运行时间会长多少呢？后者是前者的 100 倍，还是 1 000 000 倍？就像这样，我们不光要理解不同算法在运行时间上的区别，还要了解根据输入数据量的大小，算法的运行时间具体会产生多大的变化。

如何求得运行时间

那么，如何测算不同输入所导致的运行时间的变化程度呢？最为现实的方法就是在计算机上运行一下程序，测试其实际花费的时间。但是，就算使用同样的算法，花费的时间也会根据所用计算机的不同而产生偏差，十分不便。

所以在这里，我们使用“步数”来描述运行时间。“1 步”就是计算的基本单位。通过测试“计算从开始到结束总共执行了多少步”来求得算法的运行时间。

作为示例，现在我们试着从理论层面求出选择排序的运行时间。选择排序的步骤如下。

① 从数列中寻找最小值
② 将最小值和数列最左边的数字进行交换，排序结束。回到①

如果数列中有 $n$ 个数字，那么①中“寻找最小值”的步骤只需确认 $n$ 个数字即可。这里，将“确认 1 个数字的大小”作为操作的基本单位，需要的时间设为 $T_c$ ，那么步骤①的运行时间就是 $n\times T_c$ 。

接下来，把“对两个数字进行交换”也作为操作的基本单位，需要的时间设为 $T_s$ 。那么，①和②总共重复 $n$ 次，每经过“1 轮”，需要查找的数字就减少 1 个，因此总的运行时间如下。

$\begin{aligned}&(n\times T_c+T_s)+((n-1)\times T_c+T_s)+((n-2)\times T_c+T_s)+\cdots+(2\times T_c+T_s)+(1\times T_c+T_s)\\&=\frac{1}{2}T_cn(n+1)+T_sn\\&=\frac{1}{2}T_cn^2+(\frac{1}{2}T_c+T_s)n\end{aligned}$

虽说只剩最后 1 个数字的时候就不需要确认了，但是方便起见还是把对它的确认和交换时间计算在内比较好。

运行时间的表示方法

虽说我们已经求得了运行时间，但其实这个结果还可以简化。 $T_c$ 和 $T_s$ 都是基本单位，与输入无关。会根据输入变化而变化的只有数列的长度 $n$ ，所以接下来考虑 $n$ 变大的情况。 $n$ 越大，上式中的 $n^2$ 也就越大，其他部分就相对变小了。也就是说，对式子影响最大的是 $n^2$ 。所以，我们删掉其他部分，将结果表示成下式右边的形式。