问题标签 [code-complexity]

我做了一个算法来解决一个问题，但我不知道它的复杂性。该算法验证图的所有顶点是否都是“好”的。“好”顶点是可以访问图的所有其他顶点的顶点，该顶点遵循自己开始的路径。

图测试

谢谢和对不起我的英语。

嵌套for循环的时间复杂度通过两个循环O（n2）复杂度的总和进入数学推导。

对于以下三个嵌套循环的示例，我尝试了一个练习来推导如何获得 O(n3)。

简单的三个嵌套循环。

求和是 = (n + n + n + .... + n) + (n + n + n + ... + n) + ... + (n + n + n + ... + n)

= n^2 + n^2 + .... + n^2

n 次 n^2 = O(n^3)

三个嵌套循环从一开始就没有运行 n 次

以上是嵌套循环的一种非常常见的形式，我相信总和如下

= (n + (n -1) + (n -2) + (n - 3) + ... + 1) + ((n -1) + (n - 2) + (n - 3) +.. . + 1) + ((n -2) + (n -3) + (n - 4) + ... + 1) + ... + ((n - (n -2)) + 1)

= n(n - 1) /2 + (n-1) (n -2) / 2 + (n-2)(n-3)/2 + .... + 1

= 从这里我有点不确定我的逻辑是否正确。我相信上面的每一个都评估为一个最大值为 n2 的多项式，因为这就是我们在时间复杂度上所关心的，所以上面的等式分解为。

= n^2 + n^2 + n^2 +... +n^2

= 这是 n 次 n^2 = O(n^3)。

我的假设正确吗？

三个嵌套循环未从末尾运行 n 次

如果上面是两个嵌套循环，则总和将是 1 + 2 + 3 + 4 + ... + n。但是，对于三个嵌套的事件，我推断它是

= 1 + (1 + 2) + (1 + 2 + 3) + (1 + 2 + 3) + (1 + 2 + 3 + .... + n)

从这里我不确定如何推导出 O(n^3) 或如何进一步简化上述求和。

我有两个组合框，如下所示，

每当我单击done按钮时，我都会从组合框中获取值并将其存储在如下对象中，

在我使用的控制器类中，

对于具有两个组合框的设计，代码看起来很简单。我的疑问是如果组合框的数量增加怎么办？使用上述方法代码将有很多行。克服这个问题的设计是什么，我如何在这种情况下实现它？

Landscape.io提供了很好的 Python 代码测试，并且基于 PEP8、PyLint、McCabe 等。

我的一些解析器方法包含大开关块，所以我想为选定的方法禁用 McCabe 测试 MC0001。我怎样才能做到这一点？

我为 PyLint 找到了这个语法：

来源：https ://docs.landscape.io/suppressing.html

...但没有显示语法mccabe。根据我的谷歌研究，可以为项目中的所有文件禁用 McCabe 规则，但这不是我的目标。这是一个全局禁用 MC0001 的 yaml 文件：

来源：https ://0x7df.wordpress.com/tag/mccabe/

试图找到这个代码块的 Big-O 估计：

我做了一个估计并简化： O(m)O(n)O(1) => O(mn)

看起来所有情况都是 O(mn)，因为 O(1) 操作是否执行并不重要，这是正确的吗？还是有最好/最差/平均的情况？

欣赏任何见解！

谢谢

以下两种方法做同样的事情。就时间/空间复杂度而言，哪一个更有效？

设A[1...n]是一个由 n 个不同数字组成的数组。

该对(i, j)被称为逆，如果i < j and A [i] > A [j]。

例子：

A := (2, 3, 8, 6, 1) => A 有 5 个逆。

任务：

编写程序找出数组 A [1..n] 的逆数，使得算法的复杂度为 O (n * logn)。

我想降低以下算法的复杂性。基本上，它将一个单词作为输入并计算其中的唯一字母数（单词的“熵”）。我当前的解决方案使用 3 个嵌入式 for 循环，其复杂度为 o(n^3)。由于这段代码是一个更大项目的一部分（我们为名为 boggle 的游戏构建了一个求解器），我希望降低算法的复杂性以减少其执行时间。提前致谢！

我正在做一些非常接近这段代码的事情：

我试图找出的是复杂性......我发现了 O(n^3) 但我不想“接受”这个答案。基本上如果我删除 2 for(a) 循环，它会是相同的复杂性？

但实际上这些代码不会有相同的执行时间，可能不会那么接近..为什么它仍然是 O(n^3) ：/

假设您有一个整数数组（例如 [1 5 3 4 6]）。元素根据以下规则重新排列。每个元素都可以向前（向左）跳跃并在它跳跃的那些索引中滑动元素。该过程从第二个索引（即 5）中的元素开始。它可以选择跳过元素 1，也可以留在自己的位置。如果它确实选择了跳跃，元素 1 会向下滑动到索引 2。假设它确实选择了跳跃，那么我们的结果数组将是 [5 1 3 4 6]。元素 3 现在可以跳过 1 或 2 个位置并重复该过程。如果在一个位置上跳跃 3 次，则数组现在将是 [5 3 1 4 6]，如果它在两个位置上跳跃，现在将是 [3 5 1 4 6]。

很容易证明所有可能的元素排列都是可能的。此外，任何最终配置都可以通过一组独特的事件来实现。

问题是，给定一个最终数组和一个源数组，找出从源到达最终数组所需的总跳数。AO(N^2) 的实现很容易找到，但是我相信这可以在 O(N) 或 O(NlogN) 中完成。此外，如果不可能做得比 O(N2) 更好，那么很高兴知道。

例如，如果最终数组是 [3,5,1,4,6]，源数组是 [1,5,3,4,6]，则答案将为 3。

我的 O(N2) 算法是这样的：你从末尾循环遍历源数组的所有位置，因为我们知道这是最后一个要移动的元素。这里它将是 6，我们检查它在最终数组中的位置。我们计算必要的跳数，并且需要重新排列最终数组以将该元素放在源数组中的原始位置。重新排列步骤遍历数组中的所有元素，并且该过程循环遍历所有元素，因此 O(N^2)。使用 Hashmap 或 map 可以帮助搜索，但是在 O(N^2) 中的每一步之后都需要更新 map。

PS我正在尝试以贝叶斯方式对两个排列之间的相关性进行建模，这是其中的一个子问题。任何关于修改生成过程以使问题更简单的想法也是有帮助的。

编辑：我找到了我的答案。这正是 Kendall Tau 距离所做的。有一个简单的基于合并排序的算法可以在 O(NlogN) 中找到这一点。