如果我有这样的功能：

那是 n^2 的大 O 还是 n 的大 O？如果您有一个 for 循环，并且在该 for 循环内部有一个对自身的函数调用，那么 Big O 是迭代次数乘以该函数吗？

注意：我是算法分析的超级新手，所以不要将我的任何肯定作为绝对真理，我所说的任何（或一切）都可能是错误的。

嗨，我正在阅读有关算法分析和“Big-O-Notation”的内容，我对某些事情感到困惑。

假设要求您打印 char 数组的所有排列，对于 [a,b,c]，它们将是 ab、ac、ba、bc、ca 和 cb。

一种方法是（在Java中）：

如果我是正确的，这个算法有一个O(n ² )的符号。

我想到了其他方法：

现在这个算法的速度是原来的两倍，但除非我错了，否则对于大 O 表示法它也是O( ² )

它是否正确？可能不是，所以我会改写：我哪里错了？

System.currentTimeMillis() 是 Java 中时间性能的最佳度量吗？使用它来比较采取行动之前的时间和采取行动之后的时间时是否有任何问题？有更好的选择吗？

如果我有以下代码：

并且Dosomething(object)方法的时间性能是O(log n)，整体性能是IterateArrayO(n)还是O(n log n)？

在对此答案的评论中，提出了一个想法，即反转简单链表只能在 O(nlog(n)) 时间内完成，而不是 O(n) 时间。

这绝对是错误的 - O(n) 反转不是问题 - 只需遍历列表并随时更改指针。需要三个临时指针 - 这是恒定的额外内存。

我完全理解 O(nlog(n)) 比 O(n) 更差（慢）。

但出于好奇 - 用于反转简单链表的 O(nlog(n)) 算法可能是什么？具有恒定额外内存的算法是可取的。

编辑 2：对于为什么这仍然很重要的实际演示，只需看看stackoverflow 自己的正则表达式导致的中断今天（2016-07-20）！

编辑：自从我第一次提出这个问题以来，这个问题已经有了很大的发展。请参阅下面的两个快速+兼容但不完全功能的实现。如果您知道更多或更好的实现，请提及它们，这里还没有理想的实现！

我在哪里可以找到可靠快速的正则表达式实现？

有谁知道.NET或本机的正常非回溯（回溯）线性时间正则表达式实现，并且可以从.NET合理使用？System.Text.RegularExpressions为了有用，它需要：

• 正则表达式评估的最坏情况时间复杂度为O ( m*n)，其中 m 是正则表达式的长度，n 是输入的长度。
• 具有O(n) 的正常时间复杂度，因为几乎没有正则表达式实际上触发指数状态空间，或者，如果可以，仅在输入的一分钟子集上这样做。
• 具有合理的构建速度（即没有潜在的指数 DFA）
• 旨在供人类使用，而不是数学家 - 例如，我不想重新实现 unicode 字符类： .NET 或 PCRE 样式字符类是一个加号。

奖励积分：

• 如果它实现了基于堆栈的功能，可以让它以消耗 O(n+m) 内存而不是 O(m) 内存为代价来处理嵌套，那么它的实用性就会得到加分。
• 捕获子表达式或替换的奖励积分（如果有可能的子表达式匹配的指数数量，那么枚举所有它们本质上是指数的 - 但枚举前几个不应该是，替换也是如此）。您可以通过使用另一个功能来解决缺少任何一个功能的问题，因此拥有一个就足够了。
• 将正则表达式视为第一类值的很多奖励积分（因此您可以采用并集、交集、连接、否定 - 特别是否定和交集，因为这些很难通过正则表达式定义的字符串操作来实现）
• 惰性匹配，即在无限流上匹配而不将其全部放入内存是一个优点。如果流不支持查找，则（通常）不可能一次捕获子表达式和/或替换。
• 反向引用已经过时了，它们根本不可靠；即在给定病态输入案例的情况下，总是可以表现出指数行为。

存在这样的算法（这是基本的自动机理论......） - 但是是否有任何可从 .NET 访问的实际可用的实现？

背景：（可以跳过）

我喜欢使用正则表达式进行快速而肮脏的文本清理，但我反复遇到 perl/java/python/.NET 使用的常见回溯 NFA 实现显示指数行为的问题。不幸的是，一旦您开始自动生成正则表达式，这些情况就很容易触发。当您在匹配相同前缀的正则表达式之间交替使用时，即使是非指数性能也会变得非常差 - 例如，在一个非常基本的示例中，如果您将字典转换为正则表达式，预计性能会很糟糕。

要快速了解为什么存在以及自 60 年代以来存在更好的实现，请参阅正则表达式匹配可以简单快速。

不太实用的选择：

• 几乎是理想的：FSA 工具包。可以将正则表达式编译为 DFA + NFA 的快速 C 实现，也允许转换器（！），具有一流的正则表达式（封装耶！），包括交集和参数化的语法。 但它在序言中......（为什么具有这种实用功能的东西在主流语言中不可用？？？）
• 快速但不切实际：完整的解析器，例如优秀的ANTLR ，通常支持可靠的快速正则表达式。但是，antlr 的语法要冗长得多，并且当然允许可能无法生成有效解析器的构造，因此您需要找到一些安全的子集。

好的实现：

• RE2 - 一个谷歌开源库，旨在实现合理的 PCRE 兼容性减去反向引用。我认为这是作者给出的 plan9 正则表达式库的 unix 端口的继承者。
• TRE - 也主要与 PCRE 兼容，甚至可以进行反向引用，尽管使用那些你会失去速度保证。并且它有一个超级漂亮的近似匹配模式！

不幸的是，这两种实现都是 C++，并且需要从 .NET 使用互操作。

1) Reorder the following efficiency from smallest to largest: 2^n, n!, n^5, 10000, nlog2(n)

My Ans-> 10000 < nlog2(n) < n^5 < 2^n < n!

Correct ?

2) Efficiency of an algo. is n^3, if a step in this algo. takes 1 nanosec. (10^-9 sec.). How long does it take the algo. to process an input of size 1000?

I don't know ... Is it (1000)^3 * 10^-9 ?

最近在一次采访中，我被问到几个与技术问题过程中出现的各种算法的 Big-O 相关的问题。我不认为我在这方面做得很好......自从我参加编程课程以来，我们被要求计算算法的 Big-O 十年以来，我没有讨论过任何东西的“Big-O”我工作过或设计过。我与其他团队成员以及与我共事过的架构师就代码的复杂性和速度进行了许多讨论，但我从未加入过在实际项目中实际使用 Big-O 计算的团队。讨论总是“鉴于我们对数据的理解，是否有更好或更有效的方法来做到这一点？” 永远不要“这个算法的复杂性是多少”？

我想知道人们是否真的在讨论他们的代码中的“Big-O”？

我无法解决问题；有人能帮我吗？

以下语句的大 O 符号是什么：-