2021算法这么清奇:如何从数学视角优化复杂度
共 3239字,需浏览 7分钟
·
2021-07-16 00:42
复杂度
复杂度是程序时间损耗和数据总量之间的变化关系,通常用 O(f(n))
来表示,其中 f(n)
就是复杂度函数。
如果程序的时间损耗和数据量的关系是 t=c+n×b
,也就是说复杂度函数为 f(n)=c+n×b
。
复杂度通常不关注常数,因为它是个固定的时间损耗,与输入的数据总量没有任何的关系。因此,复杂度函数 c+n×b
可以忽略常数 c
和 b
,直接缩写为 f(n) = n
,即第一个例子的复杂度为 O(n)
。
如果程序的时间损耗和数据量没有关系,即 t=c
,我们依然会忽略这个常数,直接用 O(1)
来表示。
复杂度的计算与程序的结构有着密切关系。通常而言,一个顺序结构或选择结构的代码的执行时间与数据量无关,复杂度就是 O(1)
;而对于循环结构而言,如果循环的次数与输入数据量的多少有关,就会产生复杂度了。
通常,一层循环的时间复杂度是 O(n)
;如果是两个循环的嵌套,时间复杂度是 O(n2)
;如果是三个循环的嵌套,则是 O(n^3)
……
用数学来优化复杂度
设想一下,如果一段线上代码在输入变量很多的时候就会“卡死”,那么这一定是一款无法上线的系统。因此,时间复杂度的优化,是每个开发者必须具备的技能。
其实,时间复杂度的优化有很多办法。除了优化数据结构、优化代码结构、减少程序中不必要的计算等通用方法以外,还可以利用强大的数学知识来进行时间复杂度的优化。
我们来举几个例子。
在一个无序的数组中,只有一个数字
obj
出现了一次,其他数字都出现了两次,尝试去查找出这个出现了一次的obj
。
绝大多数程序员的代码逻辑,应该都是设计两层 for 循环:一层遍历每个数字,一层计算每个数字出现的次数,直到找到 obj
。
代码如下:
a = [2,1,4,3,4,2,3]
for i in range(0,len(a)):
times = 0
for j in range(0,len(a)):
if a[i] == a[j]:
times += 1
if times == 1:
print a[i]
break
读代码:
第 2 行,开始 for 循环,并把计数的变量
times
置为0
;第 4 行,嵌套了一个 for 循环;
第 5 行开始,判断里外两层循环的值是否相等,如果相等,则
times
加1
;第 7 行,判断
times
是否为1
,如果为1
说明a[i]
在数组中只出现了一次,则打印并break
跳出循环结束。
根据我们前面的结论,这段代码的复杂度是 O(n^2)
,而且单独借助数据结构等思想已经很难再进行程序的优化了。
然而,如果从数学视角来看,这段代码就可以进行如下优化:
a = [2,1,4,3,4,2,3]
result = a[0]
for i in range(1,len(a)):
result = result ^ a[i]
print result
在这里,利用了异或运算的性质:
满足交换律和结合律;
可以把相同元素计算为
0
;0
异或任何数字都是其本身。
这样,只要把数组 a 中所有元素都异或在一起,就得到了 obj
。
此时,只需要一层 for 循环,复杂度是 O(n)
。
我们再看下面一个例子。
输入一个正整数 n,求不大于 n 的所有偶数之和。例如输入 6,则输出 2、4、6 之和,为 12;输入5,则输出 2、4 之和,为 6。
这个题目的常规解法,是采用 for 循环,让 i
从 1
遍历到 n
。如果 i
为奇数,则 continue
;如果为偶数,则加到 result
变量中。
不难发现,复杂度是 O(n)
,代码如下:
import sys
n = int(sys.argv[1])
result = 0
for i in range(n+1):
if i % 2 == 0:
result += i
print result
我们再从数学的视角来看待这个问题,你就会发现这是个等差数列求和的问题,等差数列求和的公式为
其中 a1 为首项,n 为项数,d 为公差,前 n 项和为 Sn。
利用这个公式,我们可以直接写出下面的代码:
import sys
n = int(sys.argv[1])
a1 = 0
d = 2
nn = n/2 + 1
print nn * a1 + 2 * nn * (nn - 1) / d
获得输入变量
n
。求和的第一项,直接赋值为
0
。公差
d
为2
。第 6 行,求项数。例如,输入 6,则项数为 6/3+1=4 项;输入 5,则项数为 5/2+1=3 项。
调用等差数列求和公式,直接得到结果,运行截图如下:
这段代码的执行与输入数据量 n
毫无关系,因此复杂度是 O(1)
。
同样的道理,等比数列求和的代码,如果用计算机程序开发的思想,是需要一个 for 循环在 O(n)
复杂度下完成计算的。但借助等比数列求和公式,你只需要 O(1)
的复杂度就能得到结果。
小结
复杂度是程序开发中老生常谈的话题了。如果你的数学知识非常渊博,从数学的角度来降低代码复杂度也是一个不错的选择。
最后,可以练习一下:
输入一个正整数 n,求不大于 n 的所有 2 的正整数次幂的数字之和。例如,输入 17,则输出 1+2+4+8+16=31;输入 8,则输出 1+2+4+8=15。
你可以尝试两种方法来开发,分别是 O(n)
复杂度的 for 循环,和 O(1)
复杂度的等比数列求和公式。
推荐阅读:
更新不易,点个“在看”和“赞”吧(●'◡'●)!