我必须分析这个循环和其他循环,并使用Big-O表示法确定它的运行时间。
for ( int i = 0; i < n; i += 4 )
for ( int j = 0; j < n; j++ )
for ( int k = 1; k < j*j; k *= 2 )`
这是我到目前为止所知道的:
for ( int i = 0; i < n; i += 4 ) = n
for ( int j = 0; j < n; j++ ) = n
for ( int k = 1; k < j*j; k *= 2 ) = log^2 n
现在我
我在思考如何正确计算这个函数的时间复杂度:
def foo(lst):
jump = 1
total = 0
while jump < len(lst):
for i in range(0, len(lst), jump):
total += i
jump = jump * 2
return total
我假设它是O(n),其中n是列表的长度。
我们的while循环是O(n),for循环也是O(n),这意味着我们得到了2*O(n),它等于O(n)。
我说的对吗?
我试图弄清楚这个简单程序的时间复杂性是什么,但我似乎无法理解什么才是最好的方法。
我已经写下了每一行的时间复杂度。
1 public int fnA (int n) {
2 int sum = 0; O(1)
3 for (int i = 0; i < n; i++) { O(n)
4 int j = i; O(n)
5 int product = 1; O(1)
6
7
我这里有一个简短的程序:
Given any n:
i = 0;
while (i < n) {
k = 2;
while (k < n) {
sum += a[j] * b[k]
k = k * k;
}
i++;
}
其渐近运行时间为O( n )。为什么会这样呢?我知道整个程序至少会运行n次。但是我不确定如何找到log log n,内部循环依赖于k* k,所以它显然会小于n,如果它每次都是k/2,那么它就是n log n。但是,如何才能找到log log n的答案呢?
我正在试图找出这段代码的时间复杂性。
关于这些部分,我最后的结论是,“同时”部分O(logn)外部for循环必须小于100,所以它的O(1)和内部for循环是O(logn),所以我认为在最坏的情况下,这里的时间复杂度是O(logn),但我不确定。
public void foo (int n, int m) {
int i = m;
while (i > 100) {
i = i/3;
}
for (int k=i ; k>=0; k--) {
for (int j=1; j<n; j*=2) {
它只检查for循环1/3n次,所以我猜它在技术上仍然是线性的?然而,我真的不明白为什么它不是O(logn),因为很多时候,一个运行时间为O(logn)的代码最终会检查大约1/3n。O(logn)每次都会将选项除以2吗?
int a = 0;
for (int i = 0; i < n; i = i+3)
a = a+i;
我对这段代码的时间复杂性和用来查找它的逻辑感到困惑。
void doit(int N) {
for (int k = 1; k < N; k *= 2) { <----I am guessing this runs O(logN)
for (int j = 1; j < k; j += 1) { <------I am not sure how this one works.
}
}
}
我已经试过用手把它写出来了。但是我还是不明白。
谢谢您抽时间见我。
编辑:
再加上一个问题。相同的概念,不同的格式。
void do
所以我很难理解Big O Notation,我正在寻找一些例子来更好地理解它。现在让我们看一下下面的代码: `public static void main(String[] args)` {
int N = 4;
int sum = 0;
for (int i = 1; i < N; i = i*2)
{
for (int j = 1; j < N; j++)
{
sum++;
我在计算时间复杂性时遇到了困难,特别是使用while循环时:
例1:
while self.rotors == []:
for i in range(3):
rotor = input("Choose rotor {}: ".format(i + 1))
while rotor not in range(1, 6):
print("\nInvalid. You can only choose from 1 to 5 rotors.")
时间复杂度是O(Nx3xr)还是O(3)?
假设我们有一个FOR循环
int n;
for (int i = 0; i < sqrt(n); i++)
{
statement;
}
计算i的sqrt会增加循环的O(n)复杂度吗?在我的例子中,Java中的sqrt函数的时间复杂度为O(log ),这对循环的时间复杂度有什么影响?sqrt函数是应用于循环的每个序列,还是只应用一次,然后将该值存储并再次使用?
我在网上找到了这个example problem,我就是不明白作者是如何得出这个结论的。 sum1 = 0;
for(k=1; k<=n; k*=2) // Do log n times
for (j=1; j<=n; j++) // Do n times
sum1++;`
sum2 = 0;
for (k=1; k<=n; k*=2) // Do log n times
for (j=1; j<=k; j++) // Do k times
sum2++; 我知道第一个循环的运行时间是O( n ) = nlog(n
这是第一个算法。它的语法不正确:
for(i=1;i<=n;i++)
{for(j=1;j<=i;j++)
for(k=1;k<=100;k++)
{printf("hello")
}
}
}
在本例中,我们通过查看printf语句将被执行的总次数来计算时间复杂度为O(n^2)。因此,我们将k循环为每个i运行的次数从1添加到n。
第二个代码:
{int n=(2)^(2)^k //read as 2 to the power 2 to the power k
for (i=1;i
我有这个算法,我想分析时间复杂性,但我不确定我是否正确:
n = int(input("Enter Target Value: "))
x = 1
count = 0
while n != x:
if n % 2 == 0:
n /= 2
count +=1
else:
n -= 1
count +=1
print(count)
对于时间循环,n/2具有O(logn)的时间复杂度,n-1将是O(n),因此O(logn)+O(n)仍然是for循环中的O(logn)。3初始化将是O(1),因此这个alg
在处理函数中的函数时(当分析最坏的情况时),我对Big-O的工作原理感到困惑。例如,如果你有这样的东西会怎么样:
for(int a = 0; a < n; a++)
{
*some function that runs in O(n*log(n))*
for(int b = 0; b < n; b++)
{
*do something in constant time*
}
}
整个块会运行在O(n^2*log(n))中吗,因为在第一个for循环中,您有一个O(n)和一个O(n*log(n)),所以O(n*log(n))更大,因此我
这些循环的时间复杂度是多少?如果我错了,请纠正我。
这个循环是O(n^3),因为它有(n^3)次/2+1次迭代。
for (int i = 0; i < n * n * n; i+=2)
{
//body
}
和
这个循环是O(n^3 * m^2),因为它有(n^3 + 1) * (m^2 + 1)次迭代。或者这只是O(n^3),因为内部循环不是变量n?
for (int i = 0; i < n * n * n; i+=2)
{
for (int j = 0; j < m * m; j++)
{
//Body
}
}
作为一个初学者,我总是很难注意到有时简单代码的复杂性。有问题的代码是:
k = 1;
while (k <= n){
cout << k << endl;
k = k * 2;
}
一开始,我认为复杂度是O(log n),因为k= k*2行,我运行代码作为测试,跟踪它关于n的大小循环了多少次,即使是大尺寸的n,这也是相对较低的。我也非常确定它不是O(n),因为它会花更长的时间运行,但我可能错了,因为这就是我问这个问题的原因。
谢谢!