问题标签 [time-complexity]

我需要计算以下代码的时间复杂度：

是O(n^2)吗？

给定一个 *n 大小的多头无环图，其中每个节点最多有三个子节点和三个父节点，是否存在一个非指数算法来识别是否存在一个 n 长度路径，其中没有两个节点共享相同的值，并且每个一个集合的值被占？

基本上，我有一个 n*n 迷宫，其中每个空间都有一个随机值 (1..n)。我需要找到包含每个值的 n 个节点的路径（从顶部到底部）。

现在我正在使用深度优先搜索，但那是T(n) = 3T(n-1) + O(1)一个O(3^n)非理想的解决方案。

确认我的恐惧，或指出我正确的方向将不胜感激。

编辑：为了让这个更具体一点，这里是一个带有解决方案的迷宫（使用深度优先解决方案解决）。

我已经编写了一种算法，用于在复杂度为 log2(n)/5 的排序数组中进行搜索。它有用吗？

你们发现所有算法在这两个方面都有惊人的（艰难的，奇怪的）复杂性分析 - 产生的 O 表示法和分析方式的唯一性？

Project Euler和其他编码竞赛通常有最长的运行时间，或者人们夸耀他们的特定解决方案运行速度有多快。使用 Python，有时这些方法有些笨拙 - 即，将计时代码添加到__main__.

什么是分析 Python 程序运行时间的好方法？

我还没有看到任何东西，我怀疑定义“n”有困难，因为通常用于分析复杂函数的定义不止一个或两个变量。

有用于圈复杂度的分析工具，但是否有用于时间（和/或空间）复杂度的分析工具？如果是，是哪些，如果不是，为什么不呢？不可行吗？不可能的？只是有人没有解决它吗？

理想情况下，应用程序的整体复杂性（定义不同的可能“n”）以及应用程序中的每个方法

编辑：因此，由于停机问题，似乎不可能有一个精确的解决方案，但是，某种启发式近似是否可能？我意识到，出于实际目的，一个好的分析器会提供更多有用的信息，但这似乎是一个有趣的问题。

另外，一个计算某个程序子集的程序怎么样？

我正在查看 Prim 算法的Wikipedia 条目，我注意到它与邻接矩阵的时间复杂度为 O(V^2)，而其与堆和邻接列表的时间复杂度为 O(E lg(V))，其中 E 是边数和 V 是图中的顶点数。

由于 Prim 算法用于更密集的图中，E 可以接近 V^2，但是当它接近时，堆的时间复杂度变为 O(V^2 lg(V))，大于 O(V^2)。显然，与仅搜索数组相比，堆将提高性能，但时间复杂度另有说明。

算法实际上是如何随着改进而变慢的？

给定范围 [0..n^3-1] 内的 n 个整数的输入集，提供线性时间排序算法。

这是我星期四测试的评论，我不知道如何解决这个问题。

我认为是 MergeSort，即 O(n log n)。

但是，以下输出不同意：

我正在按序列号对 4 个节点的节点列表进行排序，并且排序正在进行 6 次比较。我很困惑，因为 6 > (4 log(4))。谁可以给我解释一下这个？

PS它是mergesort，但我仍然不明白我的结果。

谢谢大家的回答。谢谢汤姆纠正我的数学。

任何人都可以帮助解决这个算法的时间复杂度，以及为什么它是 O(n^2)。一步一步的解释会很有帮助，谢谢！