np完全问题。”
叶华讲解到这里的时候大家都能很好的理解,但接下来的问题对于他们来说就是不那么友好了。
“npc明显就比p类问题难,还是举个例子,贴近我们生活的,比如一个美团外卖小哥,他的家住在a点,要去n个地方送外卖,n个地点的两两距离都是已知的。那请问这个外卖小哥如何走遍每一个地点最后回到家里,保证他所走的路程是最短的呢?”
说到这里,叶华停顿了下来,拿起水杯喝上一口润润嗓子,八个学生皱眉思 考,其中数学天赋最好的宁杰也狐疑不断。
过了一段时间都没有人主动回答,意料之中的,叶华便说道:“这个题目在于,外卖小哥他首先就要面临有多少种行走路线的可能,怎么用数学描述?”
学生们都看向了叶华,后者道:“那显然,最终的结果就是n的阶乘o(n!)。所以就会看到,这复杂度可比之前讲述到的问题大太多太多了,因为o(n!)≈√2π(n/e)^n,这个数比以常数为底的指数大太多了。”
叶华旋即转身在浮空屏幕模拟的黑板上滑动:“列如19的阶乘,看上去感觉这个数不大,但是,列个式子:19!≈1.21x10^17,这个数大到