我已经阅读了一些算法书中的算法运行时,它表示为,O(n).例如,给定代码将在O(n)时间内运行以获得最佳情况并且在最坏情况下运行O(n 3).它是什么意思以及如何根据自己的代码计算它？它是否像线性时间一样,是否就像每个预定义的库函数都有自己的运行时一样,在调用它之前应该记住它？谢谢...
我正在尝试为以下代码段找到Big O运行时间:
for( i = 0; i < n * n; i++ )
for( j = 0; j < i; j++ )
k++;
由于n的乘法,或者只是O(n ^ 2),我不确定它是否是O(n ^ 3).一些帮助将不胜感激:)
我最近开始玩这个普林斯顿课程的算法,我观察了以下模式
上)
double max = a[0];
for (int i = 1; i < N; i++)
if (a[i] > max) max = a[i];
O(N ^ 2)
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
if (a[i] + a[j] == 0)
cnt++;
O(N ^ 3)
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
for (int k = j+1; k < …计算以下算法的复杂性？
我有以下代码片段:
i = 1;
while (i < n + 1) {
j = 1;
while (j < n + 1) {
j = j * 2;
}
i = i + 1;
}
请详细解释一下
我想知道解决问题的步骤,以便我可以解决这些问题
procedure matrixvector(n:integer);
var i,j:integer;
begin
for i<-1 to n do begin
B[i] = 0;
C[i] = 0;
for j<-1 to i do
B[i]<- B[i]+ A[i,j];
for j<-n down to i+1 do
C[i]<-C[i] + A[i,j]
end
end;
这是我作业的一个问题.我不太清楚如何解决这样的问题.
If T(n) = nT(n - 1) and T(1) = 3, then
a) T(n) = O(n^n)
b) T(n) = ?(n!)
c) T(n) = O(2^(nlogn))
d) none of the above
我不需要这个问题的确切答案(因为它的功课),但我想知道告诉递归函数的界限的方法.
我最近接受了采访,并被要求查找提供的整数位数.我有这样的事情:
#include <iostream>
using namespace std;
int givemCountOnes (unsigned int X) {
int count =0;
while (X != 0 ) {
if(X & 1)
count++;
X= X>>1;
}
return count;
}
int main() {
cout << givemCountOnes (4);
return 0;
}
我知道有更好的方法,但这不是问题.
问题是,这个程序的复杂性是什么？
由于它是输入中的位数,人们说这是O(n),其中n是输入中的位数.
但是我觉得既然上限sizeof(unsigned int)就是说64位,我应该说顺序是o(1).
我错了吗？
如果我的程序的时间复杂度是O(n^2)，对于 n,10^6 的大值，我如何以秒为单位表示运行时间？
我需要对此进行粗略估计以了解是否需要优化或者我可以继续我的代码....时间限制为 0.6 秒
问题不是关于时间复杂度的计算......而是关于从时间复杂度估计运行时间
如果我有这样的功能:
void myfunction(node* root)
{
for(int i = 0; i<root->children.size();i++)
{
myfunction(root->children[i]);
}
}
那是n ^ 2的大O还是n的大O？如果你有一个for循环并且在for循环中有一个函数调用它自己,那么Big O迭代次数是函数的吗？