我对竞争性编程和大 O 表示法非常陌生。
public void function(int n){
for(int i = n; i > 0; i/=3){
for(int j = 0; j < i; j++){
System.out.println("Hello");
}
}
}
这是算法。 据我所知时间复杂度。它定义了运行时间如何受到输入数量的影响。
所以如果我们举个例子 如果'n'是10。 外循环运行 log n 次,内循环运行 'i' 次。
内部循环相对于“i”而不是“n”运行。 所以我对如何计算时间复杂度有点困惑。 我认为是 O(log n)。如果我错了,请纠正我。
是 O(log n) 还是 O (n log n) 或 (n^2)。 这个你能帮我吗。 谢谢。
最佳答案
我会尽量用最简单的术语来解释
外部循环将简单地以 3 次为底运行 log(n)。
因为,i 每次都减少 3 倍。完成的总功等于:
n + n/3 + n/9 + n/27 + .... n/(3^log(n))
因为,n/3 + ... + n/(3^log(n)) 将永远小于 n
例如让 n = 100 那么,100 + 100/3 + 100/9 + 100/27 + ... = 100 + (33.3 + 11.11 + 3.7 + ...)
我们可以清楚地看到括号中的项总是小于100
整个解决方案的总时间复杂度为 O(n)。
关于java - 这个算法的时间复杂度是多少,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63227254/