O(cn) 是否至少以非渐近方式与 O(n) 一样快？
Is O(cn) at least as fast as O(n) in a non asymptotically way?
所以首先让我谈谈这个问题的动机。假设您必须找到数组中的最小值和最大值。在这种情况下，您可以通过两种方式挥手。
第一个包括遍历数组并找到最大值，然后做同样的事情找到最小值。这个解决方案是 O(2n).
第二个是只遍历数组一次并同时找到最小值和最大值。这个解决方案是 O(n).
即使时间复杂度减半，对于 O(n) 解决方案的每次迭代，您现在拥有两倍多的指令（忽略编译器如何可能优化这些指令）所以我相信他们应该采用相同的执行时间。
再举个例子。现在你需要反转一个数组。同样，您有两种方法。
第一个是创建一个空数组，遍历数据数组填充空数组。这个解决方案是 O(n).
第二个是遍历数据数组，交换第 0 个和第 n-1 个元素，然后交换第 1 个和第 n-2 个元素，依此类推 (using this strategy)，直到到达数组的中间大批。这个解是 O((1/2)n).
同样，即使时间复杂度减少了一半，每次迭代的指令数量也是原来的三倍。您正在迭代 (1/2)n 个元素，但对于每次迭代，您必须执行三个 XOR 指令。如果您不使用 XOR，而是使用一个辅助变量，您仍然需要 2 个以上的指令来执行变量交换，所以现在我相信 o((1/2)n) 实际上应该比 o(n) 更糟糕。
说了这么多，我的问题是：
忽略 space 复杂性、垃圾收集和编译器可能的优化，我可以假设具有 O(c1*n) 和 O(c2*n) 算法以便 c1 > c2，我可以确定吗给我 O(c1*n) 的算法与给我 O(c2*n) 的算法一样快或更快？
这个问题很酷，因为它可以改变我从这里开始编写代码的方式。如果“更复杂”(c1) 方式与“不太复杂”(c2) 方式一样快但可读性更强，我将坚持使用“更复杂”方式。
（我的理论计算机科学课程是几十年前的）
O(cn) 是 O(n).
它仍然是对数组的线性搜索。
根据定义，时间复杂度忽略常量。所以 O((1/2)n) == O(n) == O(2n) == O(cn).
你的例子O((1/2)n)说明了为什么会这样，因为常量可以衡量任何单位，所以比较它们是没有意义的。
你永远无法仅根据时间复杂度来判断哪个算法更快。但是，当 n 接近无穷大时，您可以判断哪个更快。由于从时间复杂度中删除了常量，因此它们将被视为相等，因此使用 O(c1n) 和 O(c2n) 即使 n 接近无穷大，您仍然无法判断哪个更快。
根据定义，如果 c1 和 c2 是常量，则 O(c1*n) === O(c2*c) === O(n)。也就是说，长度为 n 的数组的每个元素 的操作数 在这种复杂性分析中完全不相关。
它只会告诉您“它是线性的”。也就是说，如果你对一个长度为 n 的数组进行了 1 次无数次操作，那么你将对一个长度为 2*n 的数组进行了 2 次无数次操作（加上或减去一些比线性增长慢的东西）。
can I assume that having O(c1n) and O(c2n) algorithms so that c1 > c2, can I be sure that the algorithm that gives me O(c1n) is as fast or faster than the one that gives me O(c2n)?
不，一点也不。
首先，因为那里的常数在那次分析中毫无意义。没法说：无论你在 c1 和 c2 中为大 O 分析设置什么限制，它 绝对无关紧要 。整个想法是它将 丢弃 那些限制。
其次，因为它们没有告诉您任何可以让您比较两种算法 运行时间的 特定 值n.
此类复杂性分析只能让您比较算法的渐近行为。 现实世界中的问题一般不关心渐近线在哪里。
假设 A1(n) 是算法 1 对于长度为 n 的输入所需的操作数，并且 A2(n) 与算法 2 相同。您可以：
A1(n) = 10n + 900A2(n) = 100n
两者的复杂度是O(A1) = O(A2) = O(n)。对于小输入，A2 更快。对于大输入，A1 更快。它们变化的点是n == 10.
This question is cool because it can make a difference on how I start writing code from here and on. If the "more complex" (c1) way is as fast as the "less complex" (c2) but more readable, i'm sticking with the "more complex" one.
不仅如此，还有一个事实是，当您有 2 个不同的算法时 实际上 具有不同的复杂度 类（例如，线性与二次），使用复杂性更高的那个可能仍然有意义，因为它可能仍然 更快 .
例如：
A3(n) = n^2A4(n) = n + 10^20.
例如，算法 3 是二次的，而算法 4 是线性的，但它有一个恒定的巨大初始化时间。
对于大小不超过 n == 10^10、的输入，使用二次算法会更快。
您的特定问题的 所有 相关输入很可能都在该范围内，这意味着二次算法将是更好、更快的选择。
底线是：为了分析实际时间，需要运行算法对给定的输入（或给定的有界输入范围，如几乎所有现实世界的问题都是）并将其与其他算法进行比较，大 O 分析毫无意义。
另一种表达方式：您在问一个实际的“工程”问题（即，哪个选项更好/更快），但试图使用仅对“理论”分析有用的工具来回答问题。那个工具很重要，是的。但它没有机会为您提供您正在寻找的答案，这是有意设计的。
c1 > c2, can I be sure that the algorithm that gives me O(c1n) is as fast or faster than the one that gives me O(c2n)?
整个问题都在于“快”或“更快”这两个词。计算复杂性并不严格衡量我们直觉上理解的“快”。无需深入数学细节（尽管这是一个好主意：https://en.wikipedia.org/wiki/Big_O_notation），它回答了“当我的输入增长时它会变慢多快”的问题。所以如果你有 O(n^2) 复杂度，你可以粗略地预期输入的大小加倍将使你的算法花费 4 倍的时间。而对于线性复杂度，输入大 2 倍只会使时间增加一倍。如您所见，它是相对的，因此任何常量都会抵消。
总结一下：从你提出问题的方式来看，大 O 符号似乎不是这里的正确工具。
所以首先让我谈谈这个问题的动机。假设您必须找到数组中的最小值和最大值。在这种情况下，您可以通过两种方式挥手。
第一个包括遍历数组并找到最大值，然后做同样的事情找到最小值。这个解决方案是 O(2n).
第二个是只遍历数组一次并同时找到最小值和最大值。这个解决方案是 O(n).
即使时间复杂度减半，对于 O(n) 解决方案的每次迭代，您现在拥有两倍多的指令（忽略编译器如何可能优化这些指令）所以我相信他们应该采用相同的执行时间。
再举个例子。现在你需要反转一个数组。同样，您有两种方法。
第一个是创建一个空数组，遍历数据数组填充空数组。这个解决方案是 O(n).
第二个是遍历数据数组，交换第 0 个和第 n-1 个元素，然后交换第 1 个和第 n-2 个元素，依此类推 (using this strategy)，直到到达数组的中间大批。这个解是 O((1/2)n).
同样，即使时间复杂度减少了一半，每次迭代的指令数量也是原来的三倍。您正在迭代 (1/2)n 个元素，但对于每次迭代，您必须执行三个 XOR 指令。如果您不使用 XOR，而是使用一个辅助变量，您仍然需要 2 个以上的指令来执行变量交换，所以现在我相信 o((1/2)n) 实际上应该比 o(n) 更糟糕。
说了这么多，我的问题是：
忽略 space 复杂性、垃圾收集和编译器可能的优化，我可以假设具有 O(c1*n) 和 O(c2*n) 算法以便 c1 > c2，我可以确定吗给我 O(c1*n) 的算法与给我 O(c2*n) 的算法一样快或更快？
这个问题很酷，因为它可以改变我从这里开始编写代码的方式。如果“更复杂”(c1) 方式与“不太复杂”(c2) 方式一样快但可读性更强，我将坚持使用“更复杂”方式。
（我的理论计算机科学课程是几十年前的）
O(cn) 是 O(n).
它仍然是对数组的线性搜索。
根据定义，时间复杂度忽略常量。所以 O((1/2)n) == O(n) == O(2n) == O(cn).
你的例子O((1/2)n)说明了为什么会这样，因为常量可以衡量任何单位，所以比较它们是没有意义的。
你永远无法仅根据时间复杂度来判断哪个算法更快。但是，当 n 接近无穷大时，您可以判断哪个更快。由于从时间复杂度中删除了常量，因此它们将被视为相等，因此使用 O(c1n) 和 O(c2n) 即使 n 接近无穷大，您仍然无法判断哪个更快。
根据定义，如果 c1 和 c2 是常量，则 O(c1*n) === O(c2*c) === O(n)。也就是说，长度为 n 的数组的每个元素 的操作数 在这种复杂性分析中完全不相关。
它只会告诉您“它是线性的”。也就是说，如果你对一个长度为 n 的数组进行了 1 次无数次操作，那么你将对一个长度为 2*n 的数组进行了 2 次无数次操作（加上或减去一些比线性增长慢的东西）。
can I assume that having O(c1n) and O(c2n) algorithms so that c1 > c2, can I be sure that the algorithm that gives me O(c1n) is as fast or faster than the one that gives me O(c2n)?
不，一点也不。
首先，因为那里的常数在那次分析中毫无意义。没法说：无论你在 c1 和 c2 中为大 O 分析设置什么限制，它 绝对无关紧要 。整个想法是它将 丢弃 那些限制。
其次，因为它们没有告诉您任何可以让您比较两种算法 运行时间的 特定 值n.
此类复杂性分析只能让您比较算法的渐近行为。 现实世界中的问题一般不关心渐近线在哪里。
假设 A1(n) 是算法 1 对于长度为 n 的输入所需的操作数，并且 A2(n) 与算法 2 相同。您可以：
A1(n) = 10n + 900A2(n) = 100n
两者的复杂度是O(A1) = O(A2) = O(n)。对于小输入，A2 更快。对于大输入，A1 更快。它们变化的点是n == 10.
This question is cool because it can make a difference on how I start writing code from here and on. If the "more complex" (c1) way is as fast as the "less complex" (c2) but more readable, i'm sticking with the "more complex" one.
不仅如此，还有一个事实是，当您有 2 个不同的算法时 实际上 具有不同的复杂度 类（例如，线性与二次），使用复杂性更高的那个可能仍然有意义，因为它可能仍然 更快 .
例如：
A3(n) = n^2A4(n) = n + 10^20.
例如，算法 3 是二次的，而算法 4 是线性的，但它有一个恒定的巨大初始化时间。
对于大小不超过 n == 10^10、的输入，使用二次算法会更快。
您的特定问题的 所有 相关输入很可能都在该范围内，这意味着二次算法将是更好、更快的选择。
底线是：为了分析实际时间，需要运行算法对给定的输入（或给定的有界输入范围，如几乎所有现实世界的问题都是）并将其与其他算法进行比较，大 O 分析毫无意义。
另一种表达方式：您在问一个实际的“工程”问题（即，哪个选项更好/更快），但试图使用仅对“理论”分析有用的工具来回答问题。那个工具很重要，是的。但它没有机会为您提供您正在寻找的答案，这是有意设计的。
c1 > c2, can I be sure that the algorithm that gives me O(c1n) is as fast or faster than the one that gives me O(c2n)?
整个问题都在于“快”或“更快”这两个词。计算复杂性并不严格衡量我们直觉上理解的“快”。无需深入数学细节（尽管这是一个好主意：https://en.wikipedia.org/wiki/Big_O_notation），它回答了“当我的输入增长时它会变慢多快”的问题。所以如果你有 O(n^2) 复杂度，你可以粗略地预期输入的大小加倍将使你的算法花费 4 倍的时间。而对于线性复杂度，输入大 2 倍只会使时间增加一倍。如您所见，它是相对的，因此任何常量都会抵消。
总结一下：从你提出问题的方式来看，大 O 符号似乎不是这里的正确工具。