找出以下代码的时间复杂度和大O
找出以下代码的时间复杂度和大O。我对if else语句和其他bar(a)和foo(a)函数的时间复杂度感到困惑。一些朋友说它的时间复杂度是O(n^2)，还有人说它的时间复杂度将是O(n)。我还认为以下代码的时间复杂度将为O(n)，因为在for循环中有一个return语句，它将使foo和bar函数的时间都为O(1)，而main for循环将运行n次，因此时间复杂度将为O(n)。
//示例代码
public static void main(String args[]){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int sum = 0;
for(int i=0 ; i<n ; ++i){
if(i%2 != 0){
sum += foo(i , n) + foo(1+i , n);
}
else{
sum += foo(i , n) + bar(i , n);
}
}
}-
static void bar(int a , int n){
for(int i=0 ; i<n ; ++i){
for(int j=0 ; j< i ; ++j){
return a*(i+j);
}
}
}-
static void foo(int a , int n){
for(int i=0 ; i<n ; ++i){
return a*i;
}
}回答 2
Stack Overflow用户
发布于 2017-10-30 22:17:19
由于您使用迭代范例来表达算法，因此您所要做的就是计算操作的数量。
bar的复杂性是O(n^2)，因为您有"add i, j, then multiply by a“类型的n * (n + 1) / 2操作。
foo的复杂性是O(n) (“n”类型的multiply by a操作)。
在您的主循环中，一半的操作将调用foo两次，这将产生O(n^2)操作。迭代的后半部分将调用foo，然后调用bar，这将产生(n / 2) * [n + n * (n + 1) / 2]，也就是0.25.n^3 + 0.75.n^2，它是O(n^3)。
因此，您的循环的整体复杂性是O(n^3)。这通常被称为算法的时间复杂性(即使我们计算了操作的数量-其背后的直觉是考虑一组操作单元，并承认每个操作单元都将花费恒定的时间)。在我们的例子中，我们选择了算术运算+和*)。
我们也可以从内存消耗的角度来分析你的算法。在您的例子中，无论n的值是多少，所消耗的内存都是恒定的。这就是为什么我们会说相对于n，空间复杂度是O(1)。
编辑:我认为foo和bar中的“过早”的return是一个拼写错误。如果你不循环，那么foo和bar的复杂性就是O(1)__，而你的主循环是O(n)__。
Stack Overflow用户
发布于 2017-11-06 09:04:15
foo() -> O(n)，因为它来自i = 0 -> n
bar() -> O(n^2)，因为它来自j = 1 + 2 + 3 + ... + n，它是O(n^2)，如下所示：
对于main()，您将从i = 0 -> n开始，并且每个i的偶数值调用foo(n)两次。您还调用了foo(n)，但这是O(n)所做的，这不是最坏的情况，所以我们并不关心。
考虑最坏的情况bar(n)，被调用n/2次(从0到n的每隔一次)：
https://stackoverflow.com/questions/47017126
复制相似问题
腾讯云开发者
