与第四个比较,以此类推,取n个数就比较n-1次。”
“第二道题,还是给出n个数,但这道题是要求把n个数从大到小依次排序,那又需要多少步呢?”
宁杰再次不假思索的道:“需要n(n-1)/2步。”
叶华再次点头:“回答正确。宁杰同学你可以和其他的同学介绍一下计算的过程么?”
宁杰立马回答:“用刚才的办法先选出最大数需要用到n-1步,然后选出剩下的所有数中最大的数用n-2步,类推下去就是(n-1)+(n-2)+(n-3)+……一直加到最后的答案就是n(n-1)/2。”
柳玲双一看很快就看明白了,这不就是计算机编程里面的“冒泡法”嘛,黑客少女自然一看就懂,其实这些都是简单问题,在场的八个学生都能快速理解。
叶华接着讲道:“显然,随着n的增加,排序问题的难度就比之前选最大数的难度高了。n-1当这个n很大的时候,-1可以省略了,有没有无影响,数量级就是由n来决定的,第二个问题时间的数量级是由n^2决定,别的也可以省略,包括系数。”
说到这里叶华调出一块模拟黑板的浮空大屏幕,用手指替代粉笔,在色板上点了一下白色,然后在面板上罗列式子:“用渐进符号O表示,第一个问题的计算量表示为O(n),第二个问题表示为O(n^2)。两个问题一对比就发现随着n的增加O(n^2)更难一些,这很好理解,因为n^2比n大。”
叶华继续边写边说:“n、n^2、n^3等等或者它们的组合就叫多项式,这类问题就是「P=NP?问题」中的P类问题。那有没有更难的问题?当然有,比如质数问题。”
说着叶华回头看向学生们:“一个自然数a是不是质数?解决它需要多少步?笨方法就是挨个的除,从1开始除到√a,所以最多用到√a步,完整的描述就是:一个n位数的自然数a是不是质数?”
完全代入讲师角色的叶华旋即转身在浮空屏幕上继续罗列式子:“n位数的十进制数可以表示:10^n-10^(n-1),那显然质数问题就是:O(√10^2),就算是二进制数也是:O(√2^n),同学们看,随着位数n的增加质数问题是不是已经呈现指数上升了?这是很恐怖的上升趋势。”
“以上说的所有问题都有一个共同点,不管难不难,只要给一个答案去验证,就会显得容易很多,比如说:某个a不是质数,因为它可以被这个数b整除,那验算它就行了,可以在多项式时间内进行验证。那么所有这类问题就是NP类问题。”
叶华环顾八个学生,看到他们的眼神中没有任何疑惑不解,显然都理解了,对于
请收藏:https://m.caxao.com
(温馨提示:请关闭畅读或阅读模式,否则内容无法正常显示)