递归函数的复杂性（大O表示法）
我想确定两个函数的复杂性。
第一个我只需要知道我的解决方案是否正确，第二个是因为我正在努力寻找解决方案的两个递归调用，如果可能的话，最好进行工作，这样我就可以了解它是如何完成的。
第一：
def sum(list):
assert len(list)>0
if len(list) == 1:
return list[0]
else:
return sum(list[0:-1]) + list[-1]
尝试的解决方案：
T(0) = 4
T(n) = T(n-1) + 1 + c -- True for all n >0
T(n) = T(n-1) + 1 + c
= T(n-2) + 2 + 2C
= T(n-k) + k = kC --(n-k = 0 implies that k=n)
T(n) = T(0) + n + nC
= T(0) + 2nC --(T0 is nothing but 4)
= 6nC
Complexity = O(n)
第二：
def binSum(list):
if len(list) == 1:
return list[0]
else:
return binSum(list[:len(list)//2]) + binSum(list[len(list)//2:])
任何帮助将不胜感激。
当做
共有1个答案
对于第一种情况，可以使用递归函数T（n）=T（n-1）O（1）和T（0）=O（1）对时间复杂度进行建模。这显然解决了T（n）=O（n）。
这里有一个更直接、更正式的归纳证明。基本情况很简单：T（0）
对于第二种情况，您可以使用T（n）=T（n/2）T（n/2）=2T（n/2）为n建模时间复杂度
-
我在期中考试中遇到了这个问题，我不确定我的答案是O（n^2）。我想要有解释的答案，谢谢。
-
我正在学习算法和数据结构课程。 今天，我的教授说下面算法的复杂度是2n。 我一直等到课程结束，走近他，告诉他我真的相信这是一个O（n）算法，我做了计算来证明它，并想给他们看，但他继续说它不是，没有给我任何令人信服的解释。 该算法是递归的，具有以下复杂性： 我计算它是一个，这样： 让我们展开 当T中的项为1时，我们停止，即： n/（2i）=1== 替换后，我们获得 由于该算法是从关于合并排序的课程中
-
顺便说一句，我试图解决时间复杂性，我找到了O(2^n)。正确吗？
-
我很难确定简单递归方法的大O。我不知道当一个方法被多次调用时会发生什么。我想更具体地谈谈我的困惑领域，但目前我正试图回答一些硬件问题，为了不想作弊，我要求任何回复本文的人提出一个简单的递归方法，并对所述方法的大O进行简单解释。（最好是Java语言……我正在学习的一种语言。） 谢谢你。
-
我想用尽可能多的方法解决塔式料斗问题，并计算每种方法的时间复杂性（仅用于自我练习）。解决方案之一是： 我知道递归时间复杂度计算的一般想法，但我在分析注释行（在 for 循环内）时遇到了麻烦。通常我用 ）计算时间复杂度，并用一般表达式（例如 T（n-k））降低它，直到我达到基本情况并且可以用 n 表示 k，但是 for 循环的时间复杂度是多少？