java - 如何知道方法是 N 还是 N^2

Question

我经常看到你们谈论 N 方法和 N^2 方法，如果我错了，请纠正我，表明方法有多快。我的问题是：你们怎么知道哪些方法是 N，哪些是 N^2？还有：除了 N 和 N^2 之外，还有其他方法的速度指示吗？

Answer 1

这谈论了算法的复杂性（是的，这是它有多快的指标）

简而言之，它告诉输入大小为“N”的方法需要多少“操作”（操作是一个非常模糊和抽象的术语）。

例如，如果您的输入是一个列表类型的对象，并且您必须遍历列表中的所有项目，则复杂度为“N”。（通常表示为 O(N) ）。

如果您的输入是一个列表类型的对象，并且您只需要查看第一个（或最后一个），并且列表向您保证这样查看该项目是 O(1)；您的方法将是 O(1) - 独立于输入大小。

如果您的输入是一个列表，并且您需要将每个项目与其他每个项目进行比较，那么复杂性将是 O(N²) 或 O(N*log(n))

Answer 2

如果我错了，请纠正我，指出一种方法有多快。

它说明了算法将如何在理想机器上扩展。它故意忽略所涉及的因素，这可能意味着 O(1) 可能比 O(N) 慢，而 O(N) 可能比 O(N^2) 慢。例如 Arrays.sort() 将对小型集合（Java 7 中的长度 < 47）使用插入排序 O(N^2)，而不是快速排序 O(N ln N)

一般来说，使用低阶算法是一个更安全的选择，因为它们不太可能在极端情况下崩溃，而您可能没有机会彻底测试。

Answer 3

猜测程序的大 O 复杂性的方法是基于干运行代码的经验（在你的脑海中运行它）。有些情况很明显，但最有趣的情况并非如此：例如，在 O(n) 循环中调用已知为 O(n) 的库方法会导致 O(n ² ) 总复杂度；在 O(n) 循环中写入 aTreeMap会导致总计 O(nlogn)，依此类推。