对于下面的伪码,最糟糕的时间复杂度大O表示法是什么?(假设函数调用是O(1)),我对大O表示法非常陌生,所以我不确定答案,但我认为O(log(n))是因为while循环参数每次乘以2,还是仅仅是O(loglog(n))?还是我在这两方面都错了?任何输入/帮助都是值得赞赏的,我正试图掌握最糟糕的时间复杂度的大O表示法的概念,我刚刚开始学习。谢谢!
i ← 1
while(i<n)
doSomething(...)
i ← i * 2
done
我有一个问题,找到算法所需的内存的大O顺序意味着什么?
比如,这和大o操作有什么区别?
E.g
给出以下伪代码,并使用初始化的二维数组A,两维大小均为n:
for i <- 1 to n do
for j <- 1 to n-i do
A[i][j]= i + j
内存的大o符号不就是n^2,计算也是n^2吗?
试着复习一下我对“大O”的理解,以便进行一次测试(显然需要一个非常基本的“大O”理解),在我的书中,我正在做一些练习问题。
他们给了我下面的片段
public static void swap(int[] a)
{
int i = 0;
int j = a.length-1;
while (i < j)
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
我觉得很容易理解。它有两个迭代器,每个迭代器用固
所以我得到第一个for循环运行O(n)次,然后在里面运行3次,然后再运行3次。但是,我如何用大O符号来表达这一点呢?那么,2份打印声明重要吗?如何将它们添加到我的大o表达式中?谢谢,真的很困惑,也很感谢你的帮助。
for (int x = 0; x < n; x++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
printf("%d", arr[x]);
我正在尝试找出下面两个算法的大O符号,但遇到了问题。
第一个是:
public static int fragment3 (int n){
int sum = 0;
for (int i = 1; i <= n*n; i *= 4)
for (int j = 0; j < i*i; j++)
sum++;
return sum;
} //end fragment 3
答案应该是O(n^4)。当我自己尝试这样做时,我得到的结果是:我看了第一个for循环,并认为它运行了n^2 logn次。然后对于内部for循环,它运行n次+外部循环的运行时间,即n^3 logn次。我知道
我刚接触过Java,我的问题是关于大O复杂性的。
对于a),它显然是嵌套循环的O(n^2)。
for ( int i = 0; i < n; i++)
for ( int j=0; j < n; j++ )
但是,对于b),随着sum++操作的结束,以及嵌套循环的复杂性,这是否改变了它的大O复杂度呢?
int sum = 0;
for ( int i = 1; i <= n; i++)
for ( int j = n; j > 0; j /= 2)
sum++;
另一个大O符号question...What是下面代码的大O:
for (int i = n; i > 0; i = i / 2){
for (int j = 0; j < n; j++){
for (int k = 0; k < n; k++){
count++;
}
}
}
我的想法是:分解一下,我认为外部循环是O(log2(n)),那么每个内部循环都是O(n),这会导致O(n^2 * log2(n))问题#1,对吗?
问题#2:当组合嵌套循环时,它
我的印象是,为了找到嵌套的for循环的大O,一个循环将每个forloop的大O与下一个for循环相乘。大O会不会代表:
for i in range(n):
for j in range(5):
print(i*j)
是O(5n)?如果是这样的话,大O表示:
for i in range(12345):
for j in range(i**i**i)
for y in range (j*i):
print(i,j,y)
成为O(12345*(i**i**i)*(j*i)?或
我只想知道这段代码的大O执行增长率的分解,我试着计算它,但我把for循环搞错了。所以我现在完全被困在这个问题上了。
void doInter(int setA[], int setB[], int sizeA, int sizeB)
{
const int MAX = 10;
int sizeR;
int results [MAX];
// validate sizeA and sizeB
if ((sizeA == 0) || (sizeB == 0))
{
cout << "one o
我有这个数组,它有一个max堆属性。deleteMax的时间复杂度为O(logn)。如果下面的代码只迭代7次,那么下面的代码(大O)的时间复杂度是多少?
int heap_size = 15;
int i, value, heap_array[]; // array is in the form of max heap
....
for(i = 0; i < 7; i++){ // iterates seven times
value = deleteMax(heap_array);
printf("%d ", value);
}
我脑子里有两个解决办法。
与Big符号一样,"O(1)“可以描述以下代码:
O(1):
for (int i = 0; i < 10; i++) {
// do stuff
a[i] = INT;
}
O(n):
for (int i = 0; i < n; i++) {
// do stuff
a[i] = INT;
}
O(n^2):
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
所以,我真的不明白大O符号。我的任务是确定这个代码段的"O值“。
for (int count =1; count < n; count++) // Runs n times, so linear, or O(N)
{
int count2 = 1; // Declares an integer, so constant, O(1)
while (count2 < count) // Here's where I get confused. I recognize that it is a nested lo
我找到了下面的代码,用于计算a^b (破解编码访问,Ch )。(六大O)
return a * power(a, b - 1);的逻辑是什么?它是某种递归吗?是这里的关键字还是伪代码?整次幂( int a,int b) { if (b < 0) {返回a;/ error }否则,如果(b == 0) {返回1;}{返回a*幂(a,b- 1);}
我正在练习Skiena的“算法”一书,我被困在这个问题上:
我需要计算以下算法的大O:
function mystery()
r=0
for i=1 to n-1 do
for j=i+1 to n do
for k=1 to j do
r=r+1
在这里,最外层循环的大O是O(n-1),中间循环是O(n!)。如果我错了,请告诉我。
我无法计算最里面的循环的大O。
有人能帮我吗?
我正在学习大O,我偶然发现
function timesTwo(num) {
return 2 * num
}
let result = timesTwo(5) // 10
let result2 = timesTwo(2000) // 4000
然后上面写着
现在,你认为哪一个计算时间最长?2*5还是2*2000?.这只是一个运算(一个乘法)。不管输入的大小如何,函数的计算时间都是相同的。
怎么会是真的??那是怎么回事?在我看来,200亿美元将花费更长的时间。
为了让事情变得更不清楚,它接着说了这些。
function manyTimes(num) {
let total =
我对以下程序的运行时间有一个问题:问题1:
a = 0
for i = 1 to n:
if i is odd:
for j = 1 to i:
a = a + j
问题2:
k = n
while k >= 1:
k = k / 2
这两个问题使用大O和大Theta的运行时间是多少?
对于第一个问题,第一行是O(1),外部For循环是O(n)。我对内部的for循环感到有点困惑,因为它与j有关。我认为当n是大的奇数时,由于嵌套循环,它将是O(n^2)。
对于第二个问题,我认为k需要n/2次才能小于1,但不确定它是O( n )还是n的
,我将如何计算DP算法的大O。我逐渐意识到我的算法计算方法并不总是有效的。我会用简单的技巧提取出“大O”是什么。例如,如果我正在评估下面算法的非回忆录版本(删除缓存机制),我将查看递归方法在本例中3次调用自己的次数。然后,我将这个值提高到n,给出O(3^n)。对于DP,这是完全不正确的,因为递归堆栈没有那么深入。我的直觉告诉我,DP解决方案的大O将是O(n^3)。,我们将如何口头解释我们是如何得到这个答案的,。更重要的是,是一种可以用来查找类似问题的大O的技术,。既然是DP,我确信子问题的数量是很重要的,,我们如何计算子问题的数量。
public class StairCase {
p
def alg 3(n)
x = 0
i = 1
while i < n:
for j in range(0, n**3,n*3):
x += 1
i *= 3
return x
我真的不明白这段代码的大O和确切的运行时间。我最初认为大O是O(n^3) * logn,因为n**3,但n*3使我困惑。谁能解释一下这个问题吗?谢谢。