00:00
好,那么这个内容呢,咱们就讲完了啊,这个讲完之后的话呢,咱们接下来啊,给大家讲一个算法题目,这个算法题目的话呢,其实是有一定的难度的啊,这你看我写的叫经典案例哈,诶通过这个题目呢,想给大家强调一个知识点,就是说我们在平时啊,写相应的这种题目的时候,不同的实现的这种算法的操作,你会发现呢,它的性能差别是很大的。啊,那么这时候我们就通过这个呢,让大家呢去体会一下。诶,注意哈,这道题目本身稍微有点难,所以说大家你下来我是不是马上要把它这个写会呢?呃,量力而行。啊,这个题目呢,也仅代表它本身,你说你会写了,也只是会写,它本身也不具备这种迁移性啊,你说我会写它了,我就一片题目就都会了,这个不至于啊,所以说这个题目呢,你不用那么着急啊,慢慢练就行了,来我们看下这个题目呢,该如何去实现。哎,回过来。哎,我们去新建一个Java文件啊,嗯,这个呢是关于我们这个循环结构啊,条件判断,包括break这样的一些关键字的一个综合的一个题目了啊,嗯,这个呢,我们是叫。
01:07
啊,质数是吧。哎,这样写啊,关于它的一个测试。好,我把这个题目呢,就粘过来了。哎,稍微的有点难度啊,诶,CTRLCCTRLSCTRLV啊,我们保存一下看一下说呢,找出100以内所有的素数,或者呢,也叫做质数。啊,然后再接着问你说这个,诶10万以内的呢。啊,这个呢,其实算法呢是一样的哈,那我们就先以它为例吧。呃,100以内所有的素数啊。这个题目呢,如果改成100以内所有的偶数。那简单的不要不要的是吧。啊,如果呢,笔试当中让你写了一个说100以内的所有的偶数,那这个题有点侮辱你了,太简单了。你说有本事你改成素数是吧。啊,这个难度呢,可就上来了啊。好,那么首先的话呢,解决这个问题,你得清楚什么叫质数,什么叫素数啊。
02:03
平时咱叫叫哪个教的多呀。叫质数多是吧?行,那就咱就说质数吧,嗯,质数,啥是质数。对,除了一和它本身之外呢,没有其他的约数了,是吧,哎,这样数呢,咱们就叫质数啊,那我这块呢,写成一句话呢,就叫做哎,只能被一和他。本身整除的自然数是吧。哎,整除的这个自然数好,那么比如说。还记得不二三五七十一,13 17 19。二三嗯,这行点点点吧。啊,这个应该我记得上初中的时候可能还背过是吧。OK啊行啊,这时候我们知道最小的这个指数呢,是二哈。哎,这个呢,你往后顺就可以了,这呢叫做质数,那以前咱们上数学课的时候呢,一般老师都讲过,我们想证明一些定理呀,或者解决一些问题的时候呢,你最先想的一般都是定义是吧。
03:06
哎,通过定义出发呢,你去找,哎什么叫质数。啊,那这个时候呢,你看我们现在要找的是100以内所有的这个质数,那你首先呢,我们先要把100以内的这个自然数呢,先遍历一下。然后从这里边呢,去找这个质数。OK啊,行,这个便利的事儿呢,相对来说,哎比较简单啊,诶我就int一个I,这我从几开始啊。哎,咱就直接从二开始了,就。OK啊行,然后呢,I小于等于100。嗯,哎,佳佳。行,那么在这个放循环里边呢,咱们就来啊叫判定。哎,判定这个I呢,是否是指数。哎,那现在问题来了啊,怎么判断?首先想到的就是,哎,用定义行不行。只能被一和它本身整除,那你如果说去判断一个变量I说能被一和它本身整除了,就是质数也不靠谱。
04:02
所有的都能是吧。哎,这个呢,主要它有个限定条件叫智能啊。那这个智能这个事儿,其实就。直接通过定义有点难度。诶对哈,诶刚才提到说诶只能不行了,我就考虑反过来是吧,或者换句话说呢,就是咱们像高中呢,做初中也是一样啊做一些证明题啊,一些题目的时候,首先呢,你考虑的是定义,定义要不行的话呢,通常有时候会讲一些定理是吧?啊定理的推论,哎,那么这些呢,是作为我们。这个证明题啊,或者一些运算当中的一些主要的一些原则了啊好,那这个呢,我们诶换一个角度去刻画啊,就是相当于反过来哈,他既然说呢,只能被一和它本身整除,言外之意那就是从二开始。到小于这个数。呃呃,小一的这个数是吧,呃,这个范围之内呢,没有它的约束吧。哎,对啊,这个我们写一下啊,说换句话说。
05:03
哎,从二开始。啊,从二开始啊到啊这个自然数。减一啊为止。啊,不存在此自然数的约束。约束啊。你看这个呢,跟他是不是一个道理啊。好的,那么按照这句话,咱们有没有可能性把I是质数的挑出来?可以啊,可以呢,咱们试着是不是说你得让他写个for,就让这个街呢,从二开始是吧,让街呢小于。小于。对,这不就自然就是A减一了是吧,然后这个阶呢,就加加一下。哎,就这么着了。好。呃,那么在二到I减一这个范围内。我们让每一个阶是不是去除这个癌呀?
06:01
啊,那就相当于我们就,哎这咱就挨了啊,直接取模这个接那那那接着呢。你看能能这样写吗?大家注意看啊,说呢,你不是说去判断吗?说如果你要发现呢,它除不尽了。哎,我就说这个I呢,就是质数对吗。为什么?有点烧脑是吧,为什么不行?对啊,你看这个逻辑呢,是有点儿问题啊,什么问题呢,我们是说从二开始到这个自然数为止都不存在是吧。都不存在,那你现在呢,是不是只要有一个不存在,你就说是指数。比如说酒。写到这吧,比如这S9啊,S9的话,我们上来是不是让这个九去除以二了。九一除二是不是除不进,除不进,你说这就是质数,这是不是有点太武断了?哎,你应该是让二开始到八为止,这个范围之内呢,都没有它的约束,而不是说呢,只要有一个没有。
07:03
就是。所以这样呢,显然是不合适的,但是你要说这个等等它。诶等等,导师说你这块输出的都不是质数,这个事儿倒是挺挺稳妥的是吧,只要你出尽了说呃,出尽了你就不是质数啊,这这事儿倒是挺好是吧,但是我现在我找的又不是说。非质数那些数我要的是质数啊。这怎么办?插一个旗子什么意思呢?嗯。嗯。嗯。我我我大概明白你的意思了哈。啊,大概明白意思就是他提到说我们设置一个变量的一个场景是吧,就是说诶你要是出境的话呢,我我给你标识一下,说你这个事儿不靠谱了是吧。呃,然后呢,我们回过去呢,就判断说说你这个呢,有没有改过这个变量的值,通过这样的一个小的想法呢,去做这个事儿是吧?嗯,好的啊,这个方式呢,是可以的啊,那么有可能呢,很多,呃,同学呢,大家在刚开始接触的题目的时候,我没有这样一个意识哈,没有这意识的话呢,你可以在咱们咱们先一点点来哈,再换一个思路。
08:14
你看哈,他现在是说从二开始到小于一为止来减一为止啊,没有它的约束,那我能不能专门定一个变量来记录这个范围内有没有约束啊。诶刚才呢,说提到说定个旗子是吧,那个那个可能想不到啊,咱们一会儿呢,去演化到那个位置上啊,哎,我这样做大家你看能不能理解啊,诶我们进来的时候呢,在这呢,是相当于咱们在便利。哎,这个相当于是100以内的这个自然数哈,然后呢,我在这个里边呢,我定一个变量,比如说这个叫number,这个number呢,一开始是零。这个number干什么用呢?你注意看啊,它是零,一旦呢,如果我们发现那个I呢,取模接的时候等于零了,说白了这个I呢,就是被除尽了。一定要除以呢,说明这个阶呢,就是你的约束吧。
09:01
如果要是你的约束,我就让这个number呢加加一下。相当于我就记录一下,说诶你看啊,你你你增加了一个约束。然后呢,一直到这个接减I减一为止,我呢,只要你出进了,我就加加一下,相当于我就记录了从二开始到I减一这个范围内,你有几个约束。是吧,好,那么当你这个循环完了以后。我呢,在这个位置,我判断一下什么,我就知道你I是不是指数了。我怕你是不是等等于零吧,咱们要质数呢啊。对吧,哎,等点零就相当于是你根本就没有除尽过。你也没有加加过,所以呢,你就是零啊,这时候呢,我们的I不就是质数吗。哎,这个时候呢,我就把这哎打印一下,你想想是这个道理吧。哎,所以这个number的作用呢,它是来记录啊,我们这个I啊,从。哎,或者就咱就这样说吧,啊,挨着这个呃,约束的个数。
10:06
那当然这个呢,我们是从二开始啊,到这个I减一为止,这个范围内。它的一个约束的个数,那你要是没有,没有那不就是质数吗。哎,就这样。好,来保存一下这个题目,这样写是不是差不多就可以了?来我们做一个编译啊运行。Java c。嗯,Prime number的一个测试。诶,你看编译过了啊,Java。的一个测试,走起。诶,看一下诶好像没什么问题。哎,这个呢,就是我们这道题的一个做法。哎,这样的写就可以。行,那么这个呢,咱们可以啊,稍微的看作是算第一种方式吧。哎,这我在这写一下啊叫哎方式一啊好,然后接下来的话呢,我把这个呢,CTRLC啊,我再粘过来,咱们这个叫方式二啊,这个方式一跟方式二呢,主要的区别呢,哎,其实呢,就是这个位置咱们变一变。
11:10
那你看刚才呢,这个是黄少鹏是吧,哎,他提到一个说我设置一个小旗子啊,这呢是一个什么样的想法呢?哎,这个来说一下啊。是这样子的哈,就是这种想法的话呢,其实比刚才这种定义number这个呢,要稍微的难理解一些啊,但是你看我们这个number的话呢,是来记录这个约束的个数的,哎,我们其实关心的只是它是否是零。我们其实不关心你具体有几个是吧。所以说的话呢,哎,像int型的这种变量,它可以01234,它可以表示很多数哈,而我们现在其实只关心你是不是零。所以说的话呢,我们就可以不定一个int型的了,我就定一个布尔型的,我就记录你有没有。哎,比如说呢,我叫is flag先呢,是一个true。好,那么这是一个处啊,一旦呢,你在这里边儿呢,除尽了,我就把你改一下。
12:06
改成false是吧,然后呢,出来以后呢,我看一下你。是否还是处?就像刚才啊,我们这是零,我看一下你是是不是还是零这呢,哎,你是for,你是truth处,我就看你还是不是处,是不是就这意思啊。哎,所以这块呢,我们就看你是否还是处。注意这块要写这样写,千万不要写成这样了。写成这样就成啥了?那就怼成负值了啊,你就哪怕是false,是不是你也给负整数了。所以这这就错了啊,哎,你要写也得这样写,但是呢,这样写也不是推荐的,应该是。直接这样写,这是最专业的。OK,老鸟这样写是吧?好,我就看一下你是否还是处,你要是处我就输出,要是你之前处尽过,嗯,肯定不是处,你不是处,那就不是指数。哎,所以说这个写法是不是,诶跟这个其实大体原理是一样的,只不过呢,就是我们根本用不着你判断具体的是几的,我就看你是不是零,所以布尔类型就能支撑得住啊。
13:10
到期。编译运行,哎,这不是同样的道理吗?哎,就可以了。啊,稍微的体会一下这个题呢,哎,这块呢,稍微的有点难度啊好,这个完了以后呢,我再说一个小的细节啊,大家注意看这个布尔类型的变量呢,我其实把它写到里边了啊。你说我能不能把它写到。这儿呢?说不行,这为啥就不行了呢?对,首先呢,你看咱们说放到里边跟放在外边的区别啊,放到外边呢,这就定义了一个是吧,你要放到这儿的话呢,是不是每当I加加一次这个呢,是不是重新定义了一个。换句话说呢,你二到一百一共多少个数,是不是就定义多少过多少个过这个波尔星变量了是吧?显然呢,放在外边呢,感觉上要更省空间一些哈。
14:04
嗯,但是定义到这儿的时候呢,对诶刚才有同学已经说的很清楚了哈,它有问题,你看我们编译语法上可以啊,一运行呢,你发现不太对。那这个事儿怎么解释啊?对,这个flag呢,我们改过它的值是吧。啊,你比如说啊二三的时候呢,发现出来了,因为二三它都是质数,它根本就没有进到这个里边,所以说这块呢,我们判断呢,始终都是出哈,所以二三出来了,四的时候呢,显然它不是一个质数,所以你拿四去判断的时候呢,四除以二给除尽了,我把这个呢就改成是一个false了,所以四没出来。字面出来问题是你接着判断A加加变成五的时候呢?五的时候,其实你应该让这个fact呢,是不是在处的情况下呢,判断五。现在你567整个全都是false的情况下,判断你虽然没进去,但是呢,它还是一个false是吧。
15:02
所以说要想这个写到这儿,你得。对,就是我们,呃,有同学说在这儿啊,其实我们应该在考虑在这儿吧。哎,在这个位置呢,我们加一下,把它理解成了叫重置。是吧,Is flag,比如说啊,当你这个四我们判断的时候呢,你把它改成false了,说你四不是个质数,然后你得把这个重置一下,接着呢判断五。是吧,五进来呢,你看一下靠不靠谱,哎,然后呢,呃,有不靠谱的,反正是你每判断一个新的I的时候呢,你这个flag呢,得先默认是个处。才行,同样的问题,上面这个number也一样啊,你要把这个number你要放在外面的话呢,这个number你想想,如果判断四的时候,它就开始变成呃,Number就加加过了啊,你在拿五判的时候,你不能拿着number不是一不是零的这个数呢,接着去考虑加加是吧。那就不行了啊。同样的问题行,所以说这块你要写在外面呢,这个一定要记着啊,加上一个重置啊,这样的一个操作啊,再来。
16:04
哎,走起,哎,这样看都是可以的。好,这就说完了啊,诶那么这个题目呢,我们就讲完了,讲完以后的话呢,为了方便大家去理解啊,我呢,呃,稍微的形象点,我们想象一个场景啊,这个场景呢,有助于大家呢,去理解这个问题。哎,同学困了啊。精神精神。啊行,那怎么去理解呢?比如这呢是咱们的一个教室啊,这个教室呢,这有一个前门。啊,这是前门啊,这个呢是一个后门。好,现在的话呢,诶,咱们这个很多人呢,就排队站在这儿了,每个人呢,代表一个自然数啊,咱们就认为第一个哈,排头上这个呢,就是二了,一直往后排啊,一直到这个100。好了,然后现在呢,每个人呢,就进到这个屋里边儿,这个屋里边儿的话呢,依次进来,其实就相当于我们内层的这个逻辑。啊,这个屋里边儿呢,就干这个事儿啊,说每个人呢代表个数,说看看你是否是质数。好,那么就进来了,进来以后的话呢,这个flag我们理解成是什么呢。
17:04
可以想象成啊,这个大家身上穿的一个马甲吧。好,那我现在把这个flag呢,我写到这个for循环的外边了,相当于每一个I呢,共用的是同一个马甲。那就相当于二进来了,他身上穿了一个马甲。啊,穿个马甲哈,然后呢,我们在里边干什么事儿呢?诶,你代表这个数,我就从二开始到小于你这个数这个范围内呢,我去除你。我看能不能除尽。一旦要是除尽了。我呢,就在你穿的这个马甲上呢,给你打个叉。说你不是直属了。是吧,给你打个叉好,然后呢,这块呢,这个人这不就从这出去吗?他出去的时候呢,这门口呢,比如有一个。审判员吧,或者啥的是吧,对,然后他专门来看一看,说诶,我看你身上这马甲有没有打过叉是吧?诶你看一看呢,发现还是当初的那个处,说明你没打过叉,没打过叉那你就是质数,我就输出你,你要身上呢改过这个值,打过叉了,你就不是质数,我就不输出你了。
18:01
哎,所以这个人的话呢,就类似于我们这个逻辑。啊,然后呢,在这里边儿呢,相当于就是我们这个for。哎,就一个一个的这样进来进行判断啊,你注意哈,呃二三的话呢,都还好,因为二三进来时候,这个他们本身是指数,所以它这个马甲呢没有打过叉是干净的,你把这个呃出去以后呢,四的时候呢,身上打过叉,四出来以后呢,它身上这个叉呃马甲呢是有叉的,你把这个马甲呢给五的时候。是不是你得给五洗干净?你不洗干净的话呢,后边这一堆人身上全有叉是吧,所以进去的时候谁身上都有叉,那不行,所以你给他洗干净,洗干净这个事儿不就是重置吗。哎,就是这样一个道理,好,那我们刚才呢,是不是也做过把这个,哎这个布尔类型的it flag是不是放到里边这个位置的时候也演示过是吧,那放到这儿怎么理解。对。这不就是每有一个I,我们就有一个波尔变量,相当于每个人。对,发了一件马甲嘛。啊,那你二进来的时候呢,你没事,你出去了,三也没事儿,也没打岔也出去,四一看你不是这时候打一个叉出去了,五五人家穿着自己的马甲呢。
19:08
所以呢,你就没有必要重试了是吧。啊,你说我是我我我我就想洗干净,你洗干净你就加上它呢,没什么影响,你把你自己的洗干净了,反正我用的也不是你的。啊,就成这个道理了。OK啊行,这个呢,就是咱们讲的这个题目的一种实现方式。好,大家呢,稍微的去体会一下啊好,那么这个完了以后呢,诶,我们接着来看这儿哈,说呢,诶10万以内的数数怎么去计算呢。那这个事儿就很简单了,只需要把它改成10万就可以了,是吧?OK啊行啊,那这块的话呢,我们主要呢,想强调的点呢,啊,还不是说咱们这道题本身,呃,接下来才是我们要讲的重点,就是说诶我们用不同的方式来实现的话呢,这个性能有可能差别挺大的。好,下边呢,我们来测试这个性能的问题啊,为了说明这个事儿方便啊,咱们再去新建一个啊Java程序,诶我再粘过来,这个我写成叫一了,好,CTRLCCTRLSCTRLV。
20:07
哎,下面呢,是咱们要讲的这个主要的问题。哎,这呢,我们这样啊,说叫便利啊,咱就就10万啊。呃,以内的,呃,所有的。哎,数数啊,或者所有的这个质数。啊,然后呢,体会啊不同的。呃,算法实现啊,其性能的差别。哎,差别啊,OK。好,这呢,就是我们说的这个情况啊呃,咱们这时候呢,针对的是10万的数据了,那不妨我把刚才咱们写的这种方式呢,我CTRL塞一下啊,咱们粘过来。我呢,就放在这儿了。好,然后呢,放到这儿以后呢,我们把这个位置呢,改成10万。差一个是吧,行,这人就是10万了啊,便利10万以内的。哎,这个自然数好,那么便利的话呢,我们完全可以呢,把10万以内这个自然数呢,一个一个的打出来,都显示到这儿,那这块呢,其实就会显得特别的多哈,所以这个我们稍微的把它改一改,我只判断一下10万以内有多少个。
21:11
哎,比如我们用一种方式写,然后我们再换成一种方式写,咱们看这个个数是不是一样,简单来判断一下,说诶其实都是对的,然后看谁性能高。这样的一个思路啊好,那要这样的话呢,我们就可以这样来处理了,这个呢我们还留着,然后在这块呢,我去定一个叫count哈,一开始是零,它呢来记录这个质数的个数哈。哎,这个大家稍微注意一下,用它来记录这个质数的个数,哎,这块呢做判断,如果呢,你要是哎是一个质数这块我们就不输出了,我就直接来一个count。加加,对,当你整个这个for循环完了以后,我是不是在这儿。记录一下个数啊。好的。哎,质数的总个数为好,冒号以下加一个count。
22:01
哎,保存一下好了,那么这呢,我们就计算一下个数,咱们想测试一下性能,那测试性能你怎么证明说你这个快那个慢呢。看一下时间是吧,哎,所以这时候呢,我们要引入一个新的操作啊,就是我们记录一下相应的代码执行的时候花费的时间是多少。啊,那这两个变量呢,把它包不包其实都可以哈,那要不咱们就都包一下,我在这个位置啊,叫获取系统当前的时间。哎,这儿呢,我们获取一份,然后呢,当你整个这个操作执行完以后哈,其实就在这儿吧,我们也获取一下系统当前时间,让这两个时间呢减一下,看看你到底是用了多长时间。诶,这个思路呢很清楚啊好,那下边的问题就诶这个归结为我们获取这个时间用哪个操作啊这呢,我们就得看一下Java给我们提供现成的这个API了。啊,这个大家也都有啊,咱们课件都有这个时候呢,我们用的一个方法啊,是这个system系统这个类里边的。这类里边有个方法呢,叫做它。
23:01
哎,挺长的哈,叫current time。当前系统的呢,表示就毫秒的意思。哎,他这返回的就是当前啊,以毫秒来表示的这个当前的时间,哎,注意了啊,它这个方法调用完以后呢,它得到的是一个long型的值。哎,这个浪形是个数啊是吧?诶时间怎么会是个数呢?哎,这里边就提到了它返回的这个啊,哎,是用毫秒来计算的,是between什么呀,就是当前时间于1970年1月1号啊,这个00:00:00到咱们现在为止的毫秒数。啊,这这是一个计时单位啊。诶稍微注意一下,就这呢,相当于可以看到是咱们的时间的一个原点啊,就是如果我们画个数轴的话呢,就是时间不断的去流逝,这个所谓的原点呢,就是1970年的1月1号。哎,这样一个场景,行,这个呢我们就知道了啊,第二呢是这个方法,哎,那回过来啊,这个时候我们就system点啊current time。
24:04
说哇,这么长,呃,大家没必要这样写,你只需要呢,从这CTRL塞一下是吧。诶粘过来就行,哎,我为啥写呢?是因为只是想证明我会写而已,是吧,没啥用啊,哎,我们在这个idea当中,你直接1.1CU啊,直接就给你提示了啊,也不用死记硬背啊好这呢,我们得到是浪下那个叫做start啊。好,这就可以了,然后CTRLC,然后回过来,在这儿来一个叫N的结束,哎,总个数为啊,紧接着说花费的时间为。哎,时间尾。哎,冒号,哎,加上一下。N减去诶是不是就搞定了。好,这个怀着很激动的心情,我们把它跑一下啊。嗯,Java c test,注意1.java啊,编译。编译写错了,写错了吗?
25:02
啊,那number写错了。MB是吧?好编译啊,Java。Number。他一好回撤一下。啊,因为呢,这里边儿咱没有输出语句啊,所以说这时候呢,它其实是在这个循环的过程当中,需要等一等啊大家呢,应该啊,喝口水得快一点喝是吧。哎,出来了啊,一共呢是9592个花的时间呢是7209。七秒多。这个我们在这儿,哎,写一下啊。这个是9592是吧。对啊。相当于呢,就是10万以内呢,一共是有9000多个指数啊,然后呢,花的时间呢,用七秒我们把这个事儿呢,给大家搞定出来了,这个呢,看到是整个啊我们实现的这个方式一啊说呢呃此。这个啊,CTRLCCTRL v.Java啊是实现方式一下边呢,我们针对于它呢进行迭代啊。
26:02
来。新建一个Java程序,我叫二。啊,把它CTRLCCTRLSCTRLV保存,把代码呢,原封不动的先粘过来。CTRLC。啊粘过来这个我们改成是二啊词这个呢,哎,是。这个。方式一的一,呃是方式二啊。哎,针对于这个。一的一个优化啊。好,那我们来看一看,我说呀,这个操作计算10万以内的这个质数的这个操作啊,有很大的优化空间,那么大家你看一看在哪块可以优化。啊,这个如果你要不清楚的话,咱们一点看哈,你说这个时间这这肯定是没啥可优化的了啊,然后呢,这个flag也得用啊,个数呢也得记录啊,我们还要通过个数呢计划记录一下,你看你最后你这个优化完以后,你最后一不是9592,那说明你还有问题呢。
27:02
啊,这个我们要验证一下啊,所以核心的操作呢,应该是这块。哎,我们主要呢,就定位在这个区域了。在这个区域里边呢,哎,我们取这个质数呢。这块优化一下不。不用了是吧,有同学提到个优化,说可以优化,怎么优化呢?我这是从二开始到10万,他其实知道这个范围内偶数肯定不是质数。他直接呢就从二开始,或者二呢,它上边先把二呢先输出出来。他从三开始,每次呢加俩。就直接把偶数给过掉是吧,哎,只考虑奇数,说这这是一个优化,其实也算是也是个优化,确实没问题是吧,但是呢,我们其实啊,咱以后讲这个数组也好,讲这个真正的数据结构也好,实际上这种算法的话呢,以后我们会讲的概念叫做复杂度哈。从那个复杂度的这个层面来讲的话呢,如果我们从二一直到10万,这个10万呢,我们看成是一个N的话,从二到N是吧,那么你要是一个一个便利呢,它的其实呢,就是呃,跟N相关的。
28:09
然后你要是诶每隔一个便离一个呢,其实是理解成便利了二分之N次是吧,对,但是从那个复杂度的这个角度来讲呢。对,都是跟N叫同阶的是吧。诶对啊,这个呢,理工科呢,可能会更熟悉一点啊,诶同阶的就是你都是N的一次密码是吧,所以呢,我们就都看成是同一个复杂度了。啊,你说有没有区别呢?当然有区别了,二分之N时间一定少是吧?当然呢,你是同阶的呢,我就忽略掉你这个层面的这个影响了。哎,你N和N方呢,我们认为区别是挺大的是吧,哎,所以这块呢,暂且咱们,哎这个事儿的话呢,你也可以去优化一下,时间也确实会短一点,但是不明显,所以我就不考虑啊,只考虑这个。奇数的那个事儿了啊,所以这个我就不动了,这要不动的话呢,下面这个重心我们就回归到这个位置了。
29:01
那么这个位置大家你看一看。哪儿可以做优化?嗯。这个呢,你可能猛一些,看那个代码呢,它就是。很抽象的啊,很生硬的这样的一些符号了哈,哎,你可以想象一下,咱们刚才说的每个人呢,代表的是一个自然数就进来了,然后呢,就要除它了,举个例子啊,你比如说我们这个是九吧。九进来了,哎,我们是不是拿二先去除它。他身上一个马甲是吧,哎拿二一除没除尽,哎接着是不是拿三出。然后三一出出进了吧。出进来的话,哎,两把刷子咔咔往那个马甲上打了个叉,然后接着呢。你又拿四去除了。用拿五除了等等等等,一直除到把。你说这个过程。其实有点没必要了,后边哈三的时候呢。
30:02
都已经打叉了是吧。就出去呗。是吧,呃,你就已经不是指数了哈,诶可能你会觉得说,哎,这三到八这块,这这也没多少个数啊是那要是是这个这个。咱就说1万吧。你这不是10万吗?咱就说1万吧,1万的话你上来就拿个2A出。就除尽了。又已经打叉了,然后你又从三一直又除到了9999。何必呢?对,所以说呢,这块我们一旦发现呢,你。除尽了是吧。是不是就break一下就可以了?哎,这个break呢,注意我们是两层for,所以它结束的是这层for,所以呢,只是结束了,你不要再去往后除了啊,没必要了。是不是可以?哎,那么这个break呢,我说呀,只针对于哪些数据是有用的呢?
31:00
非对非质数是吧,你要本身就是质数的话呢,它根本根本就进不去是吧?诶本身要质数的话呢,还是要除的哈,诶你要本身不是质数的这些像像缩到偶数一上来,这不就咔一除二就break了吗。哎,所以说这个呢,我们它呢是针对于。哎,这个非质数是吧。才有效果哈。行啊,这个呢,我们就加上他了,加上它以后呢,其实这时候这个速度就已经会降很低了。哎,我我就先不测试了啊。测试一下也行。没啥不行的是吧,那来一下吧。编译先感受一下啊编译。呃,运行改成二啊走起。这是不是降了一个数量级啊。呃,659是吧,诶在这个基础上,诶,这个相当于是我们加上了这个break哈。659,那直接降了一个数量级,已经很夸张了。好,然后呢,接下来我们再去考虑,我说呢,还有一个位置呢,可以去考虑做优化。
32:04
在这块这个附近啊。那这段没啥说的,这不就判断吗,这个重置也得有往上移。啊,对啊,提示一下这个位置。我需要呢,从二开始,一直到你这个I减一这个范围的。哎,我说呢,其实不用,那这个范围呢,我们可以缩小一点,问题缩减到哪。根号二啊。有没有同学说认为是缩减到二分之。那就这么写的是吧。啊,那二分之A呢,其实也行,当然这个注意你判断的时候呢,这个位置我们把这个等号呢,就其实就应该考身上了是吧?呃,当然你可能没想到哈,第一个呢,呃,有同学考虑的就是二分之A,呃,还有呢,就是说认为是开根号A啊,那二分之A跟开根号上第一个就是哪个范围更小,第二个呢,说谁更准确是吧。嗯,这个2/2的话呢,跟根号A哪个更数更可能更小啊。
33:05
显然是根号二是吧,你比如说这个是100的话呢,这个是50,这个呢就变成十了。呃,尤其你这个数越来越大的时候呢,其实这个根号I呢,就它肯定要小一点啊,诶那么这个呢,准确的来讲呢,我们二分之I呢是没问题的,但是呢,它不够小是吧,其实呢还可以更小,这个呢就开根号这个I。这个开根号的操作呢,是我们ma,咱们之前调用那个随机数的操作哈,这个得用开根号,它是这样的一个方法,这个大家诶就是一看下这API呢,这里边有啊,你知道这个事儿就行啊,这呢咱们就需要的话呢,就给大家引一下啊,你也不用刻意的说啊,我就想全部都学一遍,不用啊有好多我也不熟呢啊,常用的这些呢,我们用哪个咱就引入哪个了啊好,Ma里边有个开根号的操作,这个开根号的话呢,一定要小心,这个位置呢,我们是有可能也要判断一下它的啊。所以呢,我就把它呢也留留着了。啊,你比如说这个九是吧,九的话,你除完这二之后呢,还得要除以三,三不就是相当于开根号的一个效果吗。就这个等号,你得留着啊。
34:00
好,那么首先咱们先看一看这样写行不行,然后呢,咱们再来解释为什么行啊,我把它改完以后,然后我们其实这个题目呢,就已经做完了,来我们编译。啊,来运行来看。是不是很夸张?首先没问题,其次六毫秒跟这个比一下。是吧,极其夸张啊,这个呢,是我们给他加上。哎。哎,加上我们叫is,哎点哎开方是吧,这样以后呢,变成了六毫秒,在在完全执行效果一样的情况下啊,哎,然后我们这个性能呢,你看提升的倍数是极其夸张的,所以通过这个呢,就是我们想给大家抢到点,也让大家呢有一个深刻的认识啊,就我们完成一个功能的话呢,你不同的写法,它的性能呢,真的可以差别极大。啊,你不要依赖于说说现在的这个计算机呢,已经不同于像当年比尔盖茨那个时代了啊,那个时代的程序员他们写程序的时候呢,他们会比说看谁完成同样的操作性能更高,而且呢,那个代码写的越少越好。
35:07
他们去拼那个事儿,那后来的话呢,像内存这个已经很便宜了,硬盘也很便宜了,CPU的性能也得到了极大的提升,说是不是这个时候我们就不关注于说这个算法的一个优劣呢,你就看着写吧,反正这个CPU很强大是吧?啊,那这个事儿呢,就跟咱们历史当中呢。有个成语叫南辕北辙。是不是有点像啊?啊,那哥们儿的话,他要去一个地儿是吧,然后呢,他这个正好去的方向呢,是相反,别人说你反了,他说没关系,我的马比较壮是吧。码不就是CPU嘛啊,然后你方向反着来,那绕地球一圈的,哎,这样说好像他当时还知道地球是圆的呢,是吧?啊对,就是你不能完全依赖于CPU的性能,CPU性能再强,那也经不住你这样耗是吧?诶你的算法差了,那是真还是很受影响的,所以呢,算法仍然是我们要关注的一个点啊。好,那首先呢是正确的,其次的话呢,我们看一看为什么这个行啊,这个我我我就自己来解释一下了啊,咱们把这个事儿就诶快速的走一下了,呃,为什么行呢?你看啊,诶我们假设呢,这个数我就以100为例了啊,100相对来说好说一点啊,然后呢,我们一开始的时候呢,是从二开始,一直到这个99了,诶都判断一下,看能不能除尽。
36:16
啊,就是咱们先不用考虑通过这个break去限制它啊好,那这个时候呢,我们说呢,有点多了,呃,没必要啊,那实际情况呢,我们是这样的啊,假设呢,100除以二的话呢,我们知道它对应的呃,另外的一个约束呢是50。诶,你要除以三的话呢,那得到另外一个这个数呢,肯定要小一点,可能还除不尽呢,是吧?诶你要是除以四的话呢,这个数呢,得到另外一个因子呢,就更小了,以此点点点点点点,诶最终的这个中间值是多少呢?对,就是你除以这个数等于这个数本身。啊,那不就是根号这个情况嘛,根号100这不就是十吗。哎,所以这个位置呢,就是十,那现在的话呢,我们说呢,你没有必要啊,刚才不是还想了叫二分之A嘛,没有必要到50,我说呀,你只需要呢,考虑到诶二到这个范围就可以了。
37:03
啊,为什么呢?对,是对称的,你想如果从二开始到这个范围,包括这个点啊,这个范围内如果要是有约束的话,你除以这个约束除尽了,你再除以它对应的那个数不也能除尽吗?因为除这个除尽量,它得到的不就是这个数吗?我们只判断你有没有约束这个范围,要没有这个范围,我说一定也不会有。啊,因为这块如果要有的话呢,你除尽了,那不就意味着得到那个结果不就落到这儿了吗?那这个在当初就肯定也出尽过是吧。诶,所以说这就是数学上的一个证明了哈,行,所以呢,我只需要到开根号就可以了,这呢是这道题目最简单的一种处理方案。哎,结论呢,就是我刚才说的啊,大家要体会算法的一个魅力啊好,那么这个题目说完之后呢,整个咱们这一章,哎,算是就告一段落了,诶最后这块呢,咱们再写一个小的项目啊,等一下咱们就开始写它。
我来说两句