如何确定哪个快 Big Oh Notation

Question

我正在研究下面的一个给定问题，并试图在比较 A 和 B 步骤的图表中给出我的答案，但是还有其他方法吗？假设对于一个大小为 n 的问题，算法 A 需要 1000n^3 步，算法 B 需要 2^n 步（注意胡萝卜符号 ^ 表示乘方）。对于什么规模的问题，算法 A 比 B 快（意味着算法 A 的步骤比 B 少）？

Answer 1

答案是24，你可以像下面这样写一个程序来找到它

public static void main(String[] args) {

        for (int i=1; i<100; i++){
            double b = pow(2, i);
            double a = 1000 * pow(i, 3);
            if (b> a){
                System.out.println(" i is " + i + " as a result a is " + a + " and b is " + b);
                break;
            }
        }

这是输出： i 是 24 结果 a 是 1.3824E7 和 b 是 1.6777216E7

Answer 2

如果您尝试使用 O 表示法： 1000*n^3 = O(n^3), 2^n = O(2^n), 所以理论上 O(n^3) 远小于 (2^n).

但是如果你想用精确的表达式，那么它就变成了一个纯数学问题：任何可以绘制函数的数学软件都可以告诉你什么时候函数更大，哪个函数更大。

我们使用 O 表示法的原因是为了忽略常量。这并不是因为大的隐藏常量真的可以忽略，而是因为常量的估计通常不准确——这在很大程度上取决于您的硬件和程序的细节。

如何确定哪个快 Big Oh Notation

How to determine which one is fast Big Oh Notation

data-structures

time-complexity