问题标签 [time-complexity]

您能否帮我找出 Fleury 算法（用于获取欧拉回路）的时间复杂度？

可能的重复：
属性与方法

在许多情况下，某些东西应该是属性还是方法是显而易见的，但是有些项目可能被认为是模棱两可的。

明显的属性：

• “姓名”
• “长度”

明显的方法：

• “发信息”
• “打印”

模糊的：

• “有效”/“IsValid”/“验证”
• “InBounds”/“IsInBounds”/“CheckBounds”
• “AverageChildValue”/“CalcAverageChildValue”
• “颜色饱和度”/“设置颜色饱和度”

我想我会倾向于使用模棱两可的方法，但是有人知道有助于决定这一点的规则或约定吗？例如，所有属性都应该是 O(1) 吗？属性是否应该不能更改其他数据（ColorSaturation 可能会更改 R、G、B 值）？如果有计算或聚合，它不应该是一个属性吗？

只是从学术的角度来看，（而不是因为我认为这是一个好主意）是否有理由不对属性发疯，而只是在不争论的情况下对课堂进行审讯，以及所有可以改变的事情具有单个参数且不能失败的类，一个属性？

什么更快，我应该牺牲 Linq 标准来实现速度（假设字典查找确实更快）？所以让我详细说明：

我有以下内容：

我需要根据某些属性搜索产品，例如序列号。我可以先创建一个字典，然后按如下方式填充它：

当需要查找产品时，请利用 Dictionary 查找提供的 O(1)：

或者，使用 Linq：

使用 Dict 方法的缺点当然是这需要更多的内存空间、更多的代码要编写、不太优雅等（尽管大部分都是有争议的）。假设这是非因素。我应该采取第一种方法吗？

最后，我想确认一下上述 Linq 方法的复杂性是否确实为 O(n)，我看不出它会比这更好。

MSDN 声明以下SortedSet(T).Add 方法：

如果 Count 小于内部数组的容量，则此方法是 O(1) 操作。

有人可以解释一下“怎么会”吗？我的意思是在添加新值时，我们需要找到一个正确的位置来添加一个值（将其与另一个值进行比较），并且内部实现看起来像一个具有 O (log N) 插入复杂度的“红黑树”。

在给定无限数量的处理单元和无限空间的情况下，是否有可能在合理的时间内解决 O(n!) 复杂度的问题？

O(n!) 问题的典型示例是蛮力搜索：尝试所有排列（有序组合）。

维基百科说：

选择算法：查找最小值、最大值、最小值和最大值、中值，甚至第 k 个最大元素都可以使用堆在线性时间内完成。

它所说的只是它可以完成，而不是如何完成。

你能给我一些关于如何使用堆来完成这件事的开始吗？

来自维基百科：

该算法的复杂性是 O(n(logn)(loglogn))位运算。

你是怎么做到的？

复杂性包括这个loglogn词告诉我有一个sqrt(n)地方。

假设我在前 100 个数字（n = 100）上运行筛子，假设将数字标记为复合数字需要恒定时间（数组实现），我们使用的次数mark_composite()类似于

并且要找到下一个素数（例如，7在删除所有 的倍数的数字后跳转到5），操作数将是O(n)。

因此，复杂性将是O(n^3)。你同意？

我正在做的这个程序是关于一个社交网络的，这意味着有用户和他们的个人资料。配置文件结构是UserProfile.

现在，有各种可能的 Graph 实现，我认为我使用的不是最好的。我有一个Graph结构，里面有一个指向 type 的链表的指针Vertex。每个Vertex元素都有一个值、一个指向下一个元素的指针Vertex和一个指向类型链表的指针Edge。每个Edge元素都有一个值（所以我可以定义权重和需要的任何东西）、一个指向下一个元素的指针Edge和一个指向Vertex所有者的指针。

我有 2 个示例文件，其中包含要处理的数据（以 CSV 样式）并插入到图表中。第一个是用户数据（每行一个用户）；第二个是用户关系（用于图表）。第一个文件很快被插入到图表中，因为我总是在头部插入并且有大约 18000 个用户。第二个文件需要很长时间，但我仍然在头部插入边缘。该文件有大约 520000 行用户关系，需要 13-15 分钟才能插入到图表中。我做了一个快速测试，读取数据非常快，真的是瞬间。问题在于插入。

存在这个问题是因为我有一个用顶点的链表实现的 Graph。每次我需要插入关系时，我都需要查找 2 个顶点，以便将它们链接在一起。这就是问题所在......为〜520000个关系执行此操作需要一段时间。

我应该如何解决这个问题？

解决方案 1）有人建议我将 Graph（顶点部分）实现为数组而不是链表。这样我就可以直接访问每个顶点，并且插入可能会大大减少。但是，我不喜欢使用 [18000] 元素分配数组的想法。这有多实用？我的样本数据有 ~18000，但如果我需要更少或更多怎么办？链表方法具有这种灵活性，只要有内存，我就可以拥有我想要的任何大小。但是数组没有，我将如何处理这种情况？你有什么建议？

使用链表有利于空间复杂度，但不利于时间复杂度。使用数组有利于时间复杂度，但不利于空间复杂度。

关于这个解决方案的任何想法？

解决方案 2）这个项目还要求我有某种数据结构，允许基于名称索引和 ID 索引进行快速查找。为此，我决定使用哈希表。我的表是通过单独的链接作为冲突解决方案实现的，当达到 0.70 的负载因子时，我通常会重新创建表。我将下一个表大小基于此Link。

目前，两个哈希表都持有一个指向UserProfile而不是重复用户配置文件本身的指针。那将是愚蠢的，更改数据将需要 3 次更改，这样做真的很愚蠢。所以我只是将指针保存到UserProfile. 相同的用户配置文件指针也保存为每个 Graph 中的值Vertex。

所以，我有 3 个数据结构，一个 Graph 和两个 Hash Tables，每一个都指向同一个 exact UserProfile。Graph 结构将用于查找最短路径和类似的东西，而 Hash Tables 用作按名称和 ID 的快速索引。

我正在考虑解决我的 Graph 问题是，而不是让 Hash Tables 值指向 ，而是将其UserProfile指向相应的Vertex. 它仍然是一个指针，没有更多也没有更少的空间使用，我只是改变我指向的内容。

像这样，我可以轻松快速地查找我需要的每个顶点并将它们链接在一起。这将很快插入 ~520000 个关系。

我想到了这个解决方案，因为我已经有了哈希表并且我需要它们，那么，为什么不利用它们来索引 Graph 顶点而不是用户配置文件呢？基本上是一样的，我仍然可以UserProfile很快访问，只需转到Vertex然后到UserProfile.

但是，您认为第二个解决方案与第一个解决方案相比有什么缺点吗？还是只有在第一个解决方案中胜过利弊的利弊？

其他解决方案）如果您有任何其他解决方案，我会全力以赴。但是请解释一下该解决方案与前两个相比的优缺点。我现在真的没有太多时间可以浪费在这个问题上，我需要继续这个项目，所以，如果我这样做的话改变，我需要确切地了解要改变什么，如果这真的是要走的路。

希望没有人在阅读这篇文章后睡着了并关闭了浏览器，对于大遗嘱感到抱歉。但我真的需要决定如何解决这个问题，我真的需要做出改变。

PS：在回答我提出的解决方案时，请像我一样列举它们，这样我就知道你在说什么，并且不要比我现在更迷惑我自己。

问题 1：在什么情况下O(f(n)) = O(k f(n))最合适的时间复杂度分析形式？

问题 2：从符号的数学定义开始，对于正常O数，如何证明？O(f(n)) = O(k f(n))k

对于第一个问题，我认为这是时间复杂度的平均情况和最坏情况。我对吗？我还应该写什么？

对于第二个问题，我认为我们需要在数学上定义函数。那么答案是否类似于因为乘以常数只对应k于定义中任意常数的值的重新调整O？

下面的两个程序从文件中获取 n 个整数，并计算 ath 到 bth 个整数的总和 q（问题数）次。我认为上层程序的时间复杂度比下层程序更差，但是我在计算这两种算法的时间复杂度时遇到了问题。

方案一：

方案二：

下面的程序获取从 1 到 m 的 n 个整数并对它们进行排序。同样，我无法计算时间复杂度。

程序：

具有讽刺意味的是（或不是）我无法计算自己算法的时间复杂度，但我有学习的热情，所以请编程大师帮助我！