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

在这里,利用了异或运算的性质:

  1. 满足交换律和结合律;

  2. 可以把相同元素计算为 0

  3. 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
  1. 获得输入变量 n

  2. 求和的第一项,直接赋值为 0

  3. 公差 d 为 2

  4. 第 6 行,求项数。例如,输入 6,则项数为 6/3+1=4 项;输入 5,则项数为 5/2+1=3 项。

  5. 调用等差数列求和公式,直接得到结果,运行截图如下:

这段代码的执行与输入数据量 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) 复杂度的等比数列求和公式。


推荐阅读:

前端自动化测试:测试到底测什么?

京东技术三面:React 加入 Hooks 的意义是什么?

ES 标准模块化规范概述和导入导出

低代码真的是“行业毒瘤”吗?


更新不易,点个“在看”和“”吧(●'◡'●)!

浏览 17
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报