这个程序中正确的Big-O值是多少？

Question

我试图测试我对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);

    }

}

作为一个侧面问题,为什么所有关于算法的书籍对于递归都如此重要,而在我的实践经验中,我总是使用迭代.使用递归我们可以快速耗尽内存并进行恶梦调试.

Answer 1

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

你对第三个功能的回答是不正确的; 这也是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).

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

希望这可以帮助!