这个分而治之的算法是做什么的？
分而治之算法（Divide and Conquer Algorithm）是一种解决问题的方法，它将问题分解为多个相互独立且较小的子问题，然后逐个解决这些子问题，并将它们的解合并起来得到原问题的解。
这种算法的基本思想是将大问题分解为小问题，通过解决小问题来解决大问题。它通常包含三个步骤：
- 分解（Divide）：将原问题分解为多个相互独立的子问题，这些子问题的规模较小且与原问题具有相同的结构。
- 解决（Conquer）：递归地解决这些子问题，如果子问题足够小，则直接求解。
- 合并（Combine）：将子问题的解合并起来，得到原问题的解。
分而治之算法在解决问题时具有以下优势：
- 可以将复杂的问题分解为简单的子问题，降低问题的复杂度。
- 子问题之间相互独立，可以并行求解，提高算法的效率。
- 可以通过递归的方式解决问题，简化算法的实现。
分而治之算法在各种领域都有广泛的应用场景，例如排序算法（如归并排序、快速排序）、查找算法（如二分查找）、图像处理、数值计算等。
在腾讯云的产品中，与分而治之算法相关的产品包括：
- 腾讯云函数（SCF）：腾讯云函数是一种事件驱动的无服务器计算服务，可以将复杂的任务分解为多个函数，每个函数独立运行，实现分而治之的思想。产品介绍链接：https://cloud.tencent.com/product/scf
- 腾讯云容器服务（TKE）：腾讯云容器服务是一种高度可扩展的容器管理服务，可以将应用程序拆分为多个容器，每个容器独立运行，实现分而治之的思想。产品介绍链接：https://cloud.tencent.com/product/tke
这些产品可以帮助开发者更好地应用分而治之算法解决实际问题，并提供了高效、稳定的云计算基础设施支持。
相关·内容
1回答
分而治之，分而治之的区别是什么？
从Fomin和Kratsch的精确指数算法出发，分支算法和约简算法使用两种规则：
约简规则用于简化问题实例或停止算法。
分支规则通过递归地解决问题的较小实例来解决问题实例。
对我来说，这听起来很像维基百科给出的分而治之的定义：
分治(D&C)是一种基于多分支递归的算法设计范式.分而治之算法的工作原理是递归地将一个问题分解成两个或多个相同或相关类型的子问题，直到这些问题变得简单到可以直接解决为止。
然而，当比较分支算法和约简算法时，如k-可满足性或计算最大独立集时，要对快速排序和合并排序等算法进行划分和征服，我却不这么认为
浏览 1提问于2016-12-14得票数 5
回答已采纳
我一直在学习一些与记忆相关的基本概念。
假设我有超过3 GB的数据要排序，那么是否可以在32位系统或32位JVM上对其进行排序。
这个堆必须完全驻留在RAM中，还是也可以驻留在硬盘中？
浏览 1提问于2015-06-21得票数 0
回答已采纳
3回答
堆排序是“分而治之”排序还是优先级队列排序？
另外，冒泡排序适合哪一类排序(除了可怕之外)。
我读到过堆排序通常被认为是一种“分而治之”的排序，但它也可以是优先级队列排序。严格来说是其中之一还是另一个？还是两者兼而有之呢？我找不到任何关于冒泡排序可以被考虑的东西。
浏览 2提问于2013-03-19得票数 3
回答已采纳
我有以下两个算法。我的分析表明，它们都是O(m^2+4^n)，即它们对于大数字是等价的。这样对吗？请注意，m和n是x和y的位数 def pow1(x, y):
if y == 0:
return 1
temp = x
while y > 1:
y -= 1
temp *= x
return temp def pow2(x, y):
if y == 0:
return 1
temp = pow2(x, y//2)
if y & 1: return te
浏览 52提问于2020-09-11得票数 0
回答已采纳
我正在准备一份报告，向我的同事解释算法分析的基本知识--他们中的一些人以前从未就这个问题做过讲座，但每个人都至少有几年的编程经验和良好的数学背景，所以我想我可以教这个。我可以很好地解释这些概念，但我需要一些导致因素的代码结构或模式的具体示例，以便我能够演示它们。
几何因子(n，n^2，n^3等)很容易使用相同的哨兵嵌入循环，但我不知道如何描述和展示一些不那么常见的循环。
我想包含指数(2^n或c^n)，对数(n log(n)或仅log(n))和因子(n!)演示中的因素。有哪些简短的、可教的方法可以在代码中获得这些信息呢？
浏览 2提问于2012-09-12得票数 3
回答已采纳
3回答
我知道像mergesort和quicksort这样的算法使用分而治之的范式，但我想知道为什么它能降低时间复杂度……
为什么“分而治之”的算法通常比非分而治之的算法工作得更好？
浏览 0提问于2013-03-27得票数 4
回答已采纳
2回答
我有一系列的对象。每个对象代表一个坐标范围(即一个块)。我想要的是在给定方向上找到另一个坐标附近的物体。
有没有一种方法可以做到这一点而不是一直遍历整个集合？
浏览 1提问于2008-11-05得票数 2
8回答
我想知道分而治之的技术是否总是将问题分成相同类型的子问题？对于相同的类型，我的意思是可以使用带有递归的函数来实现它。分而治之总是可以通过递归实现的吗？
谢谢!
浏览 4提问于2010-02-12得票数 13
回答已采纳
1回答
我在寻找一个计算问题，指定我们需要同时展示DnC方法和蛮力方法。我对“有缺陷的棋盘”非常感兴趣，这一点在这个问题中得到了更好的解释。
然而，虽然很容易找到和理解D&C方法，但我一直在努力寻找或创建一个蛮力方法，尽管我确实发现，朴素方法的时间复杂度为O(n^2)。
有缺陷的棋盘问题是一个有趣的问题，可以用“分而治之”的方法来解决。朴素算法的时间复杂度为O(n^2)。
来源：
我想知道在这个问题上是否没有蛮力的方法，我们怎么能找到时间的复杂性，如果有一种蛮力的方法，我想要一些关于如何解决这个问题的指导。
浏览 4提问于2021-03-12得票数 1
回答已采纳
3回答
用Python返回比较
、、、
我有这样的代码：
def isPrime(nr):
"""
Verify if a number is prime
nr - integer number, nr>1
return True if nr is prime, False otherwise
"""
div = 2 #search for divider starting from 2
while div<nr and nr % div>0:
div=div+1
#if the firs
浏览 1提问于2014-01-27得票数 0
回答已采纳
1回答
我们有一根绳子。
阿巴比
现在，我们必须检查是否存在一个子字符串，然后是另一个与第一个子字符串完全相同的子字符串。
在本例中:ABAEABABEABE
亚伯后面跟着安倍，那是两个相同的子字。
在本例中：
AAB
简单来说就是A，因为A后面跟着另一个A。
在本例中：
ABCDEFGHIJKLMNO
不存在这样的子字符串，所以答案是否定的。
我只找到了一个在O(n^2)中运行的算法。就是得到哈希和它的前缀。然后，对于每一个字母，我们简单地展开，并检查所有的单词结束在该字母。有许多字母。我们需要扩大它的次数。所以它是O(n^2)。我认为这个问题应该有一个O(n log )算法。
有谁有更好的主意吗？
浏览 2提问于2015-01-28得票数 10
5回答
一个由某种有序类型的元素组成的数组a1..n (即x<y总是defined)，我希望使用“分而治之”算法在数组中找到最小值。
这个任务的真正含义是什么？
浏览 0提问于2012-04-21得票数 2
6回答
我们总是看到(二叉树)上的操作有O( logn )最坏情况下的运行时间，因为树的高度是logn。我想知道，如果我们被告知一个算法的运行时间是logn的函数，例如m+ nlogn，我们是否可以得出结论，它肯定涉及(增强的)树？
编辑:多亏了你的评论，我现在意识到分治和二叉树在视觉上/概念上是如此相似。我从来没有把这两者联系起来。但我想到了一种情况，O(logn)不是一个分治算法，它涉及一棵没有BST/AVL/红黑树性质的树。
这是带有Find/Union操作的不相交集合数据结构，其运行时间为O(N + MlogN)，其中N是元素的数量，M是Find操作的数量。
如果我错过了什么，请告诉我，但我看
浏览 4提问于2010-02-22得票数 6
回答已采纳
1回答
我有一个大小为n的未排序数组，我需要找到k-1除数，这样每个子集都具有相同的大小(就像数组被排序之后)。
我见过这个问题的k-1=3，我想我需要中间值，这是取o(n)。但我认为我们应该这样做k次。
我想知道为什么需要o(n logk)。
例如:我有一个带有整数的未排序数组，我希望找到k‘to除数，即k-1整数，它根据值将数组拆分为k(相同大小)子数组。
如果我有[1, 13, 6, 7, 81, 9, 10, 11]，则3=k除法器是[7 ,11]除法到[1 6, 9 10 13 81]，其中每个子集都大到2并且相等。
浏览 2提问于2017-04-08得票数 0
回答已采纳
1回答
TSP分而治之
、、
我用不同的方式解决旅行推销员的问题。我已经用回溯和贪婪算法解决了它。现在我必须用分而治之的方法来解决它。我明白分而治之是如何运作的，但我不明白如何将它应用于这个问题。我试着在谷歌上寻找一些东西，但几乎一无所获。如果听到一些建议，我会非常感激的。谢谢。
浏览 7提问于2022-01-08得票数 -1
有没有人知道Lipton分离器定理在平面图算法中的一个实现？我在谷歌上找不到任何东西，这让我惊讶于它自1979年以来被引用了多少次。如果是这样的话，我可能会自己尝试实现这个算法。
浏览 3提问于2015-07-21得票数 1
回答已采纳
我想知道计算线性代数(如Ax=B )所需的最短代码(如ACM)是什么。下面是用高斯规则计算Ax=B的java代码：
public static void linearAlgebra(double[][] a , double[] b , double[] x , int n)
{
for(int j = 0 ; j<n ; j++)
{
for(int i = 0 ; i<n ; i++)
{
if(j<i)//lower triangle of A matrix
{
浏览 0提问于2018-01-26得票数 0
回答已采纳
1回答
我知道哨兵的使用在某种程度上相当于零填充(在复杂性意义上)。
对于那些不知道零填充是什么的人：
我们附加一些零(或其他一些值，不重要)使大小为2的幂，并在我们应用合并排序算法，我们消除了那些附加的零。
然而，除了零填充之外，我们还有其他方法可以摆脱哨兵吗？
浏览 5提问于2013-09-14得票数 3
问题是，
我有一个SQL DB与您的常规客户，产品，订单模式，但规模巨大。每个表有一千万行。还有一个大表，它有1亿行order_email。此表保存与订单相关的所有电子邮件通信。我已经在order_email之上实现了一个全文搜索，它工作得很好。
现在，我想扩展电子邮件搜索功能，以过滤基于其他域对象。即回答以下查询：
告诉那些发了一封电子邮件的顾客“永远不会放弃你”
显示与“更多的小马”短语相关的电子邮件订单。
实现是对lucene结果和sql结果执行一个交集/连接，但是由于所涉及的表和索引的大小，我想不出一种不遇到问题的方法。
我失败的方法
蛮力。将我的大部分DB列添加为
浏览 2提问于2013-07-24得票数 2
1回答
我想将快速排序修改为只对最上面的中间项进行排序。因此，像这样的集合9 5 7 1 2 4 6，其中5是中位数，部分排序的集合将类似于1 2 4 5 9 6 7。
template <class Comparable>
void objectSwap(Comparable &lhs, Comparable &rhs) {
Comparable tmp = lhs;
lhs = rhs;
rhs = tmp;
}
template <class Comparable>
void choosePivot(vector<Compa
浏览 2提问于2016-05-01得票数 1
2回答
我有两个整数数组，没有关于数组中元素范围的信息。我只知道两个数组m和n的长度，现在两个数组中都有一些重复项。我想从两个数组中找到最小的公共副本。假设我的内存有限，我该如何解决这个问题呢？
浏览 0提问于2011-08-04得票数 1
回答已采纳
1回答
当我们谈论分而治之时，我们总是使用递归。我已经知道分而治之是一种算法设计技术，但我有一个问题：
所有的分而治之的算法都是递归的吗，或者换一种说法，分而治之的思想是否在所有的递归中都被使用了？
我很困惑。
浏览 3提问于2012-02-03得票数 1
回答已采纳
1回答
我的合并排序实现有分而治之吗？
、、、、
在一次采访中，我被告知要编写一个基于分而治之的概念来实现合并排序的程序。
我写了下面的程序，
var myGlobalArray = undefined;
myGlobalArray = [8,4,17,2,1,32];
example01(myGlobalArray);
myGlobalArray = [48,14,17,2,11,132];
example01(myGlobalArray);
myGlobalArray = [45,14,5,2,1,12];
example01(myGlobalArray);
myGlobalArray = [45,-14,-5,2,1,-12];
浏览 2提问于2017-03-20得票数 0
1回答
我最近问了一个关于并行编程算法的问题，由于我的意图沟通能力差，这个问题很快就结束了：
我最近还问了另一个问题，特别是：
另一个问题是关于map reduce的，看看mapreduce是否是并行编程中其他概念的更具体版本。这个问题(关于一个有用的并行编程算法)更多地是关于并行编程的整个系列算法。不过你得原谅我，因为我对并行编程还很陌生，所以也许MapReduce或者是mapreduce的一种更通用的形式是“唯一”可用的并行编程构造，在这种情况下，我为我的无知道歉。
浏览 2提问于2010-03-09得票数 5
回答已采纳
1回答
我在一次非正式的考试中遇到过这个问题。
T(n)是一个递归关系
如果输入大小为n的算法的时间复杂度定义为：
T(1)=A
T(n)=T(n-1)+B时n>1
其中A和B是正定值。
然后，算法设计模式最好描述为：
A.减少和征服-正确回答
B.分裂和征服
C.二次型
D.生成和测试
T(n)收敛到T(n) = nB + A -> O(n)
答案A和B有什么区别？
为什么答案是减少和征服？
浏览 8提问于2022-07-15得票数 1
回答已采纳
3回答
我理解递归的要点以及它在非常简单的情况下是如何工作的，例如
// Make a func that that will add factorials
public long fact(long n){
if(n <= 1)
return 1;
else
return n * func(n-1)
}
我可以看到，每次调用时n都会减少，如果是n = 5，则输出将为120。在这种情况下，我理解了递归是如何工作的。
然而，当涉及到更复杂的调用时，我不能真正了解幕后发生的事情。我通常能理解代码，但不能解释为什么或者是如何发生的。E.G
public void mergeS
浏览 0提问于2017-10-22得票数 2
1回答
查找屏幕上键盘scala的击键
、、、、
我正试着用Scala来解决最近的一个面试问题。
您有一个屏幕上的键盘，它是一个6行的网格，每列5列。使用从A到Z的字母表，空格首先排列在网格行中。
您可以在屏幕键盘上使用这个输入单词。使用您的电视遥控器按左、右、上、下或确定键键入每个字符。
问题:给定一个输入字符串，找到需要按在遥控器上键入输入的键击序列。
代码实现可以在
我试着用三种不同的方法来解决这个问题。
简单的forldLeft。
def keystrokesByFL(输入: String，startChar: Char = 'A')：String ={ val = (""，startChar)
浏览 0提问于2017-05-11得票数 0
回答已采纳
在我的算法和数据结构类中，引入了第一个divide-and-conquer algorithm，即merge sort。
在执行作业算法时，我想到了几个问题。
使用分而治之范式实现的算法是否具有O(nlogn)的时间复杂度？
方法中的递归部分是否具有将运行在O(n^2)中的算法压缩为O(nlogn)的能力？
是什么使得这样的算法首先在O(nlogn)中运行？
对于(3)，我假设这与递归树和可能的递归次数有关。有人可能会用一个运行在O(nlogn)中的简单的分而治之算法来显示，它的复杂度是如何计算的呢？
干杯，安德鲁
浏览 4提问于2015-04-28得票数 22
回答已采纳
现在我开始学习Delaunay三角剖分，因为我找不到如何开始三角剖分
现在我的问题是，我们有一些云点示例，没有三角测量方法的10个点，我如何在我的点中进行三角测量
如果我使用算法(Delaunay)进行三角测量，意味着第一次或开始三角测量是如何发生的
认识的人会主动提供代码
提前感谢
浏览 0提问于2020-04-24得票数 0
1回答
我有三个点数组：
A=[[5,2],[1,0],[5,1]]
B=[[3,3],[5,3],[1,1]]
C=[[4,2],[9,0],[0,0]]
我需要最有效的方法，以找到三个点(一个为每个数组)是最接近彼此(在每个轴上的一个像素)。
我现在要做的是把一个点作为参考，比如说A[0]，然后循环所有其他的B和C点，寻找一个解决方案。如果A[0]没有给出任何结果，我将移动对A[1]的引用，以此类推。这种方法是一个很大的问题，因为如果我增加每个数组的点数和/或数组的数量，它需要太多的时间才能收敛几次，特别是如果解决方案位于数组的最后一个成员中。因此，我想知道是否有任何方法可以做到这一点，不可能
浏览 1提问于2019-05-13得票数 0
回答已采纳
5回答
据我所知，Strassen的矩阵乘法应该是最快的.但在我的测试中，分而治之的方法显然是最快的。我做错了什么吗？或者这是正确的吗？
这些指令是：“所花费的总时间除以执行算法的次数，以获得求解给定实例所需的时间。”
所以我在每种方法中都有一个单独的"counter++“，并将时间划分为"recorded / counter++”
到目前为止，这是我的时间：(按从上到下的顺序:经典，分治，strassen) (大小=矩阵的大小)
尺寸2
耗时:8660纳秒
耗时:3849纳秒
耗时:5377纳秒
大小4
耗时:24864纳秒
耗时:3080纳秒
耗时:5229纳秒
大小8
耗时:12
浏览 1提问于2012-02-13得票数 3
1回答
想象一下用Java或C++编写程序。您有一个文件，其中大约有5000行纯代码。每次您输入一个字母，并停顿片刻(想想Eclipse或Visual C++)，IDE就会在整个文件中显示一堆错误(或者可能只显示同一行，具体取决于编辑器)。我想知道的是，IDE是如何做到这一点的？我只能想象，一个每次你输入一个字母就读取整个文本文件的IDE，效率会非常低，而且当有人输入一定数量的字符时，它可能会变得非常慢。
我不是在寻找一个完整的算法解决方案或类似的东西。我正在寻找写一个非常简单的编辑器作为乐趣，我想知道我应该如何结合整个扫描文件的事情。即使我希望关键字有不同的颜色(this、class、static、
浏览 0提问于2013-06-17得票数 0
递归--我们都知道--就是这些问题之一--把你的头绕在周围感觉就像在你的编程之旅中实现了一个“里程碑”。
但在实际应用于实际问题时--仅仅了解递归的机制是不够的--我们还必须了解问题的本质，因为递归是最合适的解决方案。
所以我的问题是..。
要求解决递归的“问题模式”是什么？
递归是“分而治之”策略的一种形式，还是“代码重用”的一种形式?或者，它本身就是一种设计模式。
你能给我们举个例子来说明一个现实世界的问题吗?在这个问题上，递归是一个即时的解决方案。
-更新--
很多答案都把“真正的问题”称为树遍历，阶乘，等等。我更喜欢“真正的问题”--让我举个例子.
我们有大量文本(大约30 MB的文本
浏览 0提问于2011-07-20得票数 12
回答已采纳
1回答
使用遍历在2D网格中寻找峰值
、、、、
我们有一个n乘n的网格，这样左下角就有坐标(0,0)，右上角就有坐标(n，n)。网格中的单元格都有不同的值，我们的目标是找到一个局部峰值，它被定义为一个单元格的值大于其左、右、上和下邻居的值(即，对角相邻的单元格无关紧要)。
问题是，我们只能通过访问一个单元格来查看该单元格的值(即，我们不能检查(i，j)的值，除非首先采取(i+j)步骤从(0，0)得到它)。我们如何在O(n)步中找到局部峰值？
浏览 0提问于2016-03-01得票数 0
给定一个数字N和一个排序数组A，设计一种算法--使用Divide和Conquer方法--检查是否存在索引i和索引j，以便使A[i]*A[j] == N (如果存在返回1，如果没有返回0)。
我很难按照所需的(递归)方式进行下去。我想我只找到了一个可能的解决方案的一部分，但即使是在那里，我也不能百分之百地确定它是否正确:我认为如果数组的第一个元素和中心元素之间的乘积大于N，那么我正在寻找的数字(如果存在的话)肯定在数组的前半部分，所以我可以递归地调用该部分的函数，就像这样(我使用C)：
int productN(int A[], int i, int j, int N){
// mis
浏览 4提问于2021-06-22得票数 4
回答已采纳
1回答
我使用随机森林处理一个有监督的分类问题，并使用k-均值聚类算法对每个节点的数据进行分割。我试图计算算法的时间复杂度。据我所知，k-均值的时间复杂性是
O(n·K·I·d)
哪里
N是点数，
K是星系团数，
I是迭代的次数，并且
D是属性的数量。
k，i和d是常量或有上界，而n比这三者大得多，所以我想复杂性就是O(n)。
另一方面，随机森林是一种分而治之的方法，因此对于n个例子来说，复杂性是O(n·logn)，虽然我不确定这一点，但如果我错了，请纠正我。
为了得到算法的复杂性，我只是添加了这两件事吗？
浏览 1提问于2013-09-06得票数 0
回答已采纳
首先，如果这个问题适合这样做，我很抱歉，但是由于我使用的是密码的方法，我想我可以问任何可能知道这个问题的人。Karatsuba算法做得很好，但是也许有更好的方法。
浏览 0提问于2013-02-23得票数 2
我希望在具有以下两个条件的数组中找到元素的计数：
1 <= i<j <= n
ai > aj
我正在使用以下代码，但我需要一个更快的代码，有什么建议吗？
for(int i=0; i<n; i++){
for (int j=i+1; j<n; ++j){
if (a[j] < a[i])
ans++;
}
}
浏览 1提问于2020-01-11得票数 0
回答已采纳
2回答
我一直在尝试寻找某种算法来解决我所遇到的问题。我遇到的最接近的东西是装箱算法，但我不认为它是我正在寻找的安静的东西。
本文档是我的问题和预期输出的图形表示：
我的想法是在哪里找到最低(高度)的矩形，并创建一个适合其余矩形宽度的矩形，然后通过一些递归计算出其余的。
我基本上要做的是找出最小数量的垂直堆叠的矩形，给定N个水平放置的矩形。
在Java语言中，我有一个带有输入矩形的HashMap。
有什么想法，代码，链接吗？谢谢
浏览 0提问于2012-04-24得票数 1
回答已采纳
1回答
在nxn的二维数组中，我试图找到一个比它的邻居更大的数字。我使用分而治之的算法来解决这个问题。
接下来，我试图通过展示一个合适的不变量来证明我的算法的正确性，即我通过用随机数填充4x4网格，划分它，并为所选的每一列找到全局最大值(不确定这是证明算法的正确性的方法)
我最困惑的一点是如何分析我的算法的运行时间，即在最坏的情况下需要访问nxn数组中的多少个元素，以及是否有一种方法来显示算法是否无症状最优。
浏览 30提问于2017-02-27得票数 1
1回答
Scala负载平衡和检索
、、、
我有一个很大的邻接矩阵，我想把工作分配给每个参与者，比如说100个索引。
有没有办法像我们在MPI中那样将工作负载分配给不同的参与者(使用MPI_Scatter() )
有没有办法像MPI (MPI_Broadcast/ MPI_Broadcast)那样减少/广播结果。
我能想到的一种粗鲁的方法是传递整个矩阵，然后将索引传递给每个参与者，但这将违背使用参与者的目的。此外，如果我真的喜欢这样，如果演员在远程位置也不是一个好主意。
任何建议都会有很大帮助。
谢谢
浏览 0提问于2014-04-14得票数 0
1回答
给出n个整数的数组A0…N∀i,0≤i<n 1，我们有|Ai−Ai+1|≤1，给定x=A，y=An−1，我们有x<y，在O(log n)中，找到任何指数j，例如Aj=z，对于给定的z，x≤z≤y。
在我看来，这个问题限制了相邻元素之间的-difference或“距离”最多为1，但据我所知，这并不意味着数组是有序的，确实存在任意大小的子序列，它们可以遵循升序或降序，但正因为这个原因，我看不到使用算法搜索O(log )中的索引的明确方法。
我在想一些能满足这些限制的例子：
1,2,1,2
-1，0，1，1，2，1，1，1，3
4，5，6，7，8，9，10，12，13，13，13，12，
浏览 3提问于2022-04-29得票数 0
如果我有一台有多个处理器的机器，并且试图解决一个巨大的问题，那么哪种算法最适合解决这个问题？
动态规划，贪婪还是分而治之？
浏览 1提问于2016-12-20得票数 0
回答已采纳
1回答
我相信这是相当简单的，这就是为什么我非常沮丧。我在一次面试中得到了这段代码，有人问我代码计算的是什么，以及复杂性是什么。我还是很困惑。我试着写下输出作为2的基数，但我仍然没有找到一个模式。代码如下：
def mystery(n):
if n == 0:
return 0
if n % 2 == 0:
return mystery(n/2)
else:
return mystery(2(n-1)) + 1
我知道第二行是测试它何时是平均的，然而，我仍然不理解这个函数的总体功能。有什么想法吗？**编辑:将A改为神秘。
浏览 11提问于2019-11-06得票数 0
回答已采纳
编辑：
事实证明，慢版本实际上是插入排序O(n^2)，而不是解释性能问题的合并排序O(n log )。我想我可以为将来的读者省去费力地浏览代码来发现这个答案的痛苦。
原作从这里开始
我用haskell编写了两个版本的合并排序，我无法理解为什么其中一个比另一个快1000倍。在这两种情况下，我们首先将列表中的项排序为列表，创建列表列表。然后我们将列表配对并合并，直到只剩下一个列表。问题似乎是，我在慢速版本中调用"doMerge ( x1 : x2 :xs) = doMerge $ merge x1 x2: doMerge xs“，而在快速版本中调用doMerge (mergePairs
浏览 0提问于2013-08-21得票数 8
回答已采纳
免责声明:我知道这个问题可以通过数组的一次传递非常有效地解决，但我对分而治之感兴趣，因为它与我们用分而治之处理的典型问题略有不同。
假设给定一个大小为n和区间长度为l的浮点数组X1:n，问题是设计一种分而治之的算法，从具有最大和的数组中找到长度为l的子数组。
下面是长度为n的with.For数组，有n-l+1的l个连续元素的子数组。例如，对于长度n= 10和l= 3的数组，将有8个长度为3的子数组。
现在，为了将问题分成两半，我决定在n-l+1/2处分解数组，这样等数量的子数组将被分配到我的除法的两个部分，如下面的算法所示。同样，对于n= 10，l= 3，n-l+1 = 8，我在(n-l+1)
浏览 1提问于2016-10-10得票数 1
2回答
给定一个“线程”列表，其中包含两个变量--启动时间和结束时间--实现一个函数，该函数将在某个时候返回所有正在运行的线程。(比O(n)快)
我的解决方案是遍历列表--即O(n)。这里有人知道如何比O(n)更快地实现吗？
class MyThread{
Thread thread;
long start;
long end;
}//the object in the list
//function to find "threads"
public List<Thread> matchingInterval(List<MyThread> list) {
浏览 3提问于2012-04-17得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频活动推荐
腾讯云开发者
