我的时间复杂度回溯，以找到非邻接最大和的最优解
我试图对非相邻元素的最大和进行动态规划回溯，以构造得到最大和的最优解。
假设输入列表为[1,2,3,4,5]
回忆录应为[1,2,4,6,9]
我的最大值是9，对吗？
>
我发现第一次出现备忘录中的最大总和（因为我们可能不会选择最后一项）[this is O（N）]
然后我找到使用此公式选择的前一项：
max\u sum-=a\u列表[索引]
在这个例子中，9-5=4，4在索引2上，我们可以说前面选择的项目是“3”，它也在输入列表的索引2上。
我的解决方案的第三步是在while循环中完成的，假设非相邻约束是1，当列表长度为5时，我们必须回溯的最大量是3倍，大约是N//2倍。
但是第三步，使用Python的索引函数来查找前一个_和的第一次出现[O（N）]memo。索引（that\u previous\u sum）
所以总时间复杂度约为O（N//2*N）
这是O（N^2）！！！
我的时间复杂性正确吗？还是我错了？有没有更有效的方法来回溯记忆列表？
P、 对不起，如果我做错了格式，谢谢！
共有1个答案
- 我从后面循环检查前面的物品是否相同
- 如果相同，则表示它不是第一次出现。如果不是，则是第一次出现。
- Tada！从第一个索引中找不到Python的索引函数！我们现在从后面找到它
所以总时间复杂度约为O（N//2*N）
现在是O（N//2 1），即O（N）。
-
如何计算这些回溯算法的时间复杂度，它们是否具有相同的时间复杂度？如果不一样怎么办？请详细解释并感谢您的帮助。 我实际上有点困惑，对于断字(b)，复杂度是O(2n)，但对于哈密顿循环，复杂度是不同的，对于打印相同字符串的不同排列，以及对于解决n皇后问题，复杂度是不同的。
-
对于回溯算法，计算空间（堆栈空间）和时间复杂度的好方法是什么？ 我们希望输出组合的长度正好是K，并且sol集必须是唯一的 输入：arr:[1,2,3,4,5]k:4 输出： [1,2,3,4]//[2,1,3,4]无效,因为它==[1,2,3,4] 最差的时间复杂度是O(n^k)，其中n是数组的长度。
-
给定不同整数的问题，生成所有子集。https://www.interviewbit.com/problems/subset/ 我找到了两种解决方案。 第一个解决方案:: 第二种解决方案： t（n）=2t（n-1）c（即2个大小为n-1的递归调用，每个n都有一些恒定的时间）t（n）=O（2^n）通过解决上述递归关系。 但对于第二个解，我无法定义递归关系以最终使用反向替换来获得时间复杂度，并且无法通过
-
在长度为N的数组中求和最大的邻接子数组。 输入格式： 输出格式： 返回一个整数，表示相邻子数组的最大可能和。 制约因素： 输入2:A=[-2,1,-3,4,-1,2,1,-5,4] 产出2：6 说明2：子数组[4,-1,2,1]的最大可能和为6。 你能告诉我为什么下面的代码不起作用，代码中的错误是什么吗：
-
所以，我刚刚进行了一次在线编程评估，给了我两个问题，其中一个是这个连续的子数组和提供了两个复杂的编码问题+8个MCQ，并将在1小时内完成。 这里我将讨论上面提到的子数组的最大邻接和之一。通常，我发现困难的部分是处理负数和连续。我所做的是首先将应用到给定的数组，然后再次按照负值的绝对值排序，就像i的例如，对于给定的随机数组，我在每个i和所有j迭代后都有一个max，如果max 。
-
Dijkstra算法的这种特殊实现的时间复杂度是多少？ 我知道这个问题的几个答案是，当你使用最小堆时，O（E log V），这篇文章和这篇文章也是如此。然而，这里的文章说的是O（V ElogE），它的逻辑与下面的代码类似（但不完全相同）。 算法的不同实现可以改变时间复杂度，我试图分析下面实现的复杂性，但是像检查和忽略中的重复顶点这样的优化让我怀疑自己。 以下是伪代码： 笔记： 从源顶点可到达的每个