找求整数n的因子的算法只需要找到n/2是为什么

这是一道分治策略章节课后习题不过课上同学提出了一种线性复杂度的方法,我对算法的研究不多因此格外感兴趣。

总的思想是系统通过对撞消除每一对不同的数,留下重复次数最多的数

有没有大佬给答案的... 有没有大佬给答案的?

可以这样理解递归分解到最后一层是n个四

上一层是n/2个4,再上一层n/4个4一直往上

全部加起来是2n-1个4

时间复杂度忽略掉常数是O(n)的

噗,这玩意谁知道他让写4(2n-1)啊还是8n-4啊还是O(n)。会算就行了,这种试题没啥意义

你对这个回答的评价是

被查找的数是第1个数则需用第1個数和被查找的数比较,要比较1次
被查找的数是第2个数,则需用第1个数、第2个数和被查找的数比较要比较2次。
被查找的数是第n个数則需用第1个数、第2个数、...、第n个数和被查找的数比较,要比较n次

我要回帖

更多关于 计算n阶行列式典型例题 的文章

 

随机推荐