1

我想知道这个的大 O 符号是什么。我知道 for 循环是 O(n)。我不确定 if 语句是否为 O(n log n)。如果是这样，那不会使运行时间复杂度 (n)*((n log n)^3)。还是 ((n^2)(log^3n)) ？另外我知道数组中的存储是 O(n) 并且想知道调用同一数组中的元素是 O(n) 还是具有不同的运行时间复杂性。（用Java eclipse编写）

    for (i=0;i<numberOfProblems;i++){                       
    String string1= ap.nextString("P or NP?");
    if(string1=P){
        pOrNPValue[i]=0;
    }else{
        pOrNPValue[i]=1;


        String string2 = ap.nextString("Best Case Run Time?");

        if(string2==ok){
            bestCaseValue[i]=0;
        }else if(string2=oLogLogN){
            bestCaseValue[i]=1;
        } else if(string2=oLogN){
            bestCaseValue[i]=2;
        }else if(string2=oNC){
            bestCaseValue[i]=3;
        }else if(string2=oN){
            bestCaseValue[i]=4;
        }else if(string2=oNLogStarN){
            bestCaseValue[i]=5;
        }else if(string2=oNLogN){
            bestCaseValue[i]=6;
        }else if(string2=oNK){
            bestCaseValue[i]=7;
        }else if(string2=oCN){
            bestCaseValue[i]=8;
        }else if(string2=oNFactorial){
            bestCaseValue[i]=9;
        }

        String string3 = ap.nextString("Average Case Run Time?");

        if(string3=ok){
            averageCaseValue[i]=0;
        }else if(string3=oLogLogN){
            averageCaseValue[i]=1;
        } else if(string3=oLogN){
            averageCaseValue[i]=2;
        }else if(string3=oNC){
            averageCaseValue[i]=3;
        }else if(string3=oN){
            averageCaseValue[i]=4;
        }else if(string3=oNLogStarN){
            averageCaseValue[i]=5;
        }else if(string3=oLogLogN){
            averageCaseValue[i]=6;
        }else if(string3=oNK){
            averageCaseValue[i]=7;
        }else if(string3=oCN){
            averageCaseValue[i]=8;
        }else if(string3=oNFactorial){
            averageCaseValue[i]=9;
        }

        String string4 = ap.nextString("Worst Case Run Time?");

        if(string4=ok){
            worstCaseValue[i]=0;
        }else if(string4=oLogLogN){
            worstCaseValue[i]=1;
        } else if(string4=oLogN){
            worstCaseValue[i]=2;
        }else if(string4=oNC){
            worstCaseValue[i]=3;
        }else if(string4=oN){
            worstCaseValue[i]=4;
        }else if(string3=oNLogStarN){
            worstCaseValue[i]=5;
        }else if(string4=oLogLogN){
            worstCaseValue[i]=6;
        }else if(string4=oNK){
            worstCaseValue[i]=7;
        }else if(string4=oCN){
            worstCaseValue[i]=8;
        }else if(string4=oNFactorial){
            worstCaseValue[i]=9;
4

1 回答 1

2

字符串比较所花费的时间与两个字符串中较长者的长度成正比（在最坏的情况下，您只需要比较直到该点的字符）。由于此处进行的所有字符串比较都是针对常量字符串的，因此每次比较单独花费时间 O(1)。由于只有固定数量的比较，如果为真，每个比较都 O(1) 工作（无论索引如何，数组访问都需要时间 O(1)），所有比较所需的总时间为每次迭代 O(1) . 因此，完成的总工作量是 O(n)：有 O(n) 次循环迭代，每个迭代都做 O(1) 次工作。

（从技术上讲，您需要考虑从用户那里读取字符所完成的工作，这可能是无限的，因为用户可以无限期地按住一个键。我现在将通过假设总数有一个固定限制来忽略这一点用户可以在每个提示符下键入的字符数。）

一般来说，比较本身需要 O(1) 时间，真正的问题是需要多少工作来评估布尔表达式。

希望这可以帮助！

于 2013-10-02T16:34:25.337 回答