1

我正在尝试测试我对 BigO 的了解不是很自信也不是完全文盲，但请指导。

这不是家庭作业，我不是任何地方的学生，但有兴趣理解这个和其他各种相关概念。

//What is bigO of this Application ?
public class SimpleBigOTest {

    // What is BigO of this method -> I am certain it is O(n) but just checking
    private void useItirativeApprachToPrintNto0(int n) {
        for (int i = 0; i < n; i++) {
            System.out.println("useItirativeApprachToPrintNto0: " + i);
        }
    }

    // What is BigO of this method -> I am reasonabily certain it is O(n)
    private void useRecurrsiveApprachToPrintNto0(int n) {
        if (n != 0) {
            System.out.println("useRecurrsiveApprachToPrintNto0: " + n);
            useRecurrsiveApprachToPrintNto0(n - 1);
        }

    }

    // What is BigO of this method -> I think now it is O(n^2)
    private void mutltipleLinearItirationsDependentOnValueOfN(int n) {
        int localCounter = n + n;
        for (int i = 0; i < localCounter; i++) {
            System.out.println("mutltipleLinearItirationsDependentOnValueOfN: "
                    + i);
        }
        for (int i = 0; i < n; i++) {
            System.out.println("mutltipleLinearItirationsDependentOnValueOfN: "
                    + i);
        }
    }

    // What is BigO of this method -> I think this is again O(n)
    private void mutltipleLinearItirationsNotDependentOnValueOfN(int n, int j) {
        int localCounter = j;
        for (int i = 0; i < localCounter; i++) {
            System.out
                    .println("mutltipleLinearItirationsNotDependentOnValueOfN: "
                            + i);
        }
        for (int i = 0; i < n; i++) {
            System.out
                    .println("mutltipleLinearItirationsNotDependentOnValueOfN: "
                            + i);
        }
    }

    // What is bigO of this main -> I would say O(n^2) because
    // mutltipleLinearItirationsDependentOnValueOfN has biggest BigO of O(n^2)
    // if I am correct
    public static void main(String[] args) {
        SimpleBigOTest test = new SimpleBigOTest();
        int n = 1000;
        int j = 1234;
        test.useItirativeApprachToPrintNto0(n);

        test.useRecurrsiveApprachToPrintNto0(n);

        test.mutltipleLinearItirationsDependentOnValueOfN(n);

        test.mutltipleLinearItirationsNotDependentOnValueOfN(n, j);

    }

}

作为一个附带问题，为什么所有关于算法的书籍都如此高度评价递归，而在我的实践经验中，我一直使用迭代。使用递归，我们可以快速耗尽内存并进行噩梦般的调试。

4

2 回答 2

12

你对前两个的答案是正确的。

您对第三个功能的回答不正确；这也是 O(N)。原因是第一个循环迭代了2N次，第二个循环迭代了N次。这总共是 3N 次迭代，并且 3N = O(N)，因为 big-O 忽略了常数因素。

您对第四个功能的回答也不正确；这是O（N + J）。函数的运行时可能依赖于多个参数，这里就是这种情况。大大增加 N 或 J 将导致运行时更多地依赖该参数而不是另一个。许多重要的算法，如 Dijkstra 算法、KMP 字符串匹配算法等，都有依赖于多个参数的运行时。一些算法的运行时间取决于它们产生的值（这些有时称为输出敏感算法）。在分析或设计算法时牢记这一点是很好的。

最后，main 的复杂度是 O(1)，因为您调用的所有四个函数都具有固定的参数值。因为程序总是做完全相同的工作量（一些常数）。如果您允许 n 和 j 随命令行参数而变化，那么运行时间将为 O(n + j)，但由于它们是固定的，因此复杂度为 O(1)。

最后一点，我建议不要这么快放弃递归。递归是一种非常有用的算法设计技术，许多递归算法（快速排序、归并排序等）使用很少的堆栈空间并且非常实用。通过允许您以不同的方式思考问题的结构，递归思维通常可以帮助您设计迭代算法。此外，许多主要的数据结构（链表、树、尝试等）都是递归定义的，理解它们的递归结构将有助于您编写对它们进行操作的算法。相信我，这是一个很好的技能！:-)

希望这可以帮助！

于 2012-06-02T03:16:18.830 回答
2

关于复杂性分数@templatetypedef 已经提供了正确的一次。现在针对您关于递归与循环的问题。现实世界中的许多问题都具有递归行为，可以使用此属性进行最佳设计。例如河内塔，递归提供了一个非常简单的解决方案，而如果你使用一些迭代方法，那么它会变得非常复杂:(

最后递归确实有一些额外的参数开销。如果您需要极其优化的行为，那么您必须在其中做出决定。

最后，请记住，程序员的时间比 CPU 时间更昂贵。在对代码进行微优化之前，测量一下它是否真的会成为一个问题确实是个好主意。

于 2012-06-02T05:54:56.123 回答