问题标签 [code-complexity]

我想知道是否有人知道任何论文或工作笔记来计算 Scalapack 例程执行了多少操作，尤其是它们发送了多少消息以及多少字。

在操作计数方面，我总是可以浏览 Golub 和 Van Loan 的优秀矩阵计算或检查 Lapack 的 LAWN 41 并假设它们对于 ScaLapack 没有太大变化，但我找不到任何关于消息和字数的信息，这是我之前的最后手段通过代码。

我只是解决了一个问题，但我没有解决方案，所以请问您是否可以确认我的解决方案是否正确

我必须在 BIGTHETA 中找到那部分代码的复杂性。

所以，我分析第三个周期就是这样长大的

k -> 线性直到 = h（h 像 2^w 一样长大） - 所以复杂度是 log n。

关于第二个，第一个周期的限制是 0，所以我认为复杂度是 log n。

关于第一个 2^N = 2^N-1 所以复杂度是 n

总复杂度为 n * log n

此代码采用未排序的数组并使用插入排序对其进行排序。当重复项以未排序的数组排列在一起时，由于多次移位的复杂性提高到O(N^2)，我试图O(N)通过确保在重复项排列在一起的情况下没有项目移动超过一次来做到这一点。

但是，当重复项没有排列在一起时，复杂性仍然存在O(N^2)。O(N)在这种情况下我们也可以使复杂性变得更复杂吗？

我正在寻找强调其简单性的简单对象的术语。具体来说，没有自引用、不包含方法、绑定等（即 JSON 可序列化）的对象。

现在我用这样的词：

1. “平面物体”
2. “简单对象”
3. “数据容器对象”
4. “JSON 可序列化对象”

我不喜欢它们，因为：

1. 意味着缺乏层次结构，这实际上很好。
2. 似乎很模糊。
3. 也显得模糊。
4. 不是直接提到复杂性，更多的是强调需求。JSON-serializability 实际上并不经常是一个要求，而简单性却是。

我要描述的对象示例：

我想区分的对象示例：

问题

我应该怎样称呼没有自引用、不包含方法、绑定等（即 JSON 可序列化）的对象？

我最近一直在玩flog，它是一个非常好的工具，可以为 ruby​​ 应用程序生成代码复杂性报告。作为 flog在项目代码库上运行的结果，您将获得类似于以下内容的输出：

上面的示例提供了一个方法的分数，并在定义该方法的源代码中引用了确切的行号。这可以是常规实例/类方法或任何其他“动态”方法，例如。耙任务等。

因此，目标是从源文件中提取一段代码（很可能是一个方法），该代码段以 flog 输出中定义的行号开头。然后可以在某些 Web UI 中使用该片段来显示各种代码指标（基于其他工具，如flay）和/或存储在数据库中。据我所知，这个任务涉及将 ruby​​ 代码解析为 AST，然后通过树找到相应的起始行并计算出结束行号。我已经用这个库做了一些实验 - https://github.com/whitequark/parser，大部分时间都可以工作，但要获得正确的结果有点棘手。

是否有任何其他解决方案可以从用 ruby​​ 编写的源文件中快速提取方法代码？

我的朋友在一次采访中遇到了一个问题，他被告知有一个 O(n) 的解决方案。然而，我们谁也想不出来。这是问题：

有一个字符串只包含(and )，找到最长的有效括号子字符串的长度，它应该是格式正确的。

例如")()())"，最长有效括号为()()，长度为 4。

我用动态编程解决了这个问题，但不是 O(n)。有任何想法吗？

此代码用于找出给定列表中给定元素的位置。

为了找出它的复杂性，我想到了filter一个函数 isg和一个 list [0..length-1]。

现在，我不知道positions2会是什么复杂性，(n)或者由于filter功能会发生任何循环。

请建议是否有任何其他方法可以编写更紧凑的代码以降低复杂性。

现在我正在尝试在 Python 函数中找到“基本步骤”。基本步骤是代码中的点，O(1)它本身就是复杂的。我很难在这个函数中找到它：

我想认为这里的基本步骤实际上是total += numbers[i]*numbers[j]因为它应该比函数中的任何其他语句执行更多次，但是我并不完全相信我有能力弄清楚它。任何帮助表示赞赏！

我有一个简单的算法任务，我想练习我的复杂性分析，我希望得到一些确认我是正确的。

任务是；实现一个函数，该函数接受一个 size 的数组n，并返回k最大值。实施应该是时间和空间有效的。

这是我的伪代码：

1. 创建一个大小为 k + 1 的二进制最小堆。
2. 对于数组中的每个数字；
   • 将值推送到堆上。
   • 如果堆大小现在大于 k，则弹出最小值。
3. 从堆中弹出所有值并返回结果数组。

这是我对每个步骤的时间复杂度分析：

1. 微不足道。
2. 上）
   • O(log n)
   • 微不足道
3. 好的）

所以总复杂度应该是 O(n.log n + k)？空间复杂度应该是 O(k + 1)？

此外，欢迎对我的方法提出任何批评。

提前致谢！

所以我不是 CS 专业的，很难回答有关程序大（O）复杂性的问题。

我编写了以下例程来输出数组中总和为 0 的数字对：

现在，如果有人问这种方法的复杂性，我知道，因为第一个循环遍历所有n项目，它将超过（除非我错了），但有人可以解释如何找到正确的复杂性吗？

如果有更好更有效的方法来解决这个问题？