我需要比较链接列表与数组最坏的运行时间。
如果必须保留排序,并且列表/数组已经有n个项,那么对于以下情况,最坏的运行时间是什么?为什么?
以下是我的问题和答案:
Adding an item to the front of a linked list. ANSWER ATTEMPT: O(1)
Adding an item to the front of a standard array. ANSWER ATTEMPT: O(n)
Accessing the (n/2):th item of a linked list. ANSWER ATTEMPT: O(n)
Accessing the
int a = 0, b = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
a = a + j;
}
}
for (k = 0; k < N; k++) {
b = b + k;
}
我正试图计算出上述问题的时间复杂性。
我以为是O(n^2 + n),我的推理是:
n^2 : nested for loops
n : Adding the single loop
然而,确定的答案是O(n
在我开始之前澄清一下,这不是家庭作业,而是我在为考试而复习。我已经给出了以下问题的解决方案。我想要一些建设性的反馈。
感谢在我上一个问题中留下它的人的反馈。下面我给出了详细的解决方案,为什么我认为答案是这样的。
用O(n)表示法找出运行时间。
int y=0;
for(int j=1; j*j<=n; j++)// runs from 1->j=sqrt(n) times
y++; //constant - c
因此,运行时是c x n^1/2 = O(n^1/2)
Q2。
int b=0;
for(int i=n; i>0; i--) //runs from n-&
我有以下代码:
for ( int i = 1; i < n; i ++)
for ( int j = 0; j < n*n; j ++)
if (j % i == 0)
for (int k = 0; k < j; k++)
sum++;
if (j % i == 0)将如何影响整体的复杂性?当k上升到j,即n*n时,第三个循环的复杂度也应该是n*n= O(n^2),对吗?所以会是O(N)*(N^2)*(N^2)= O(n^5)?但是给出的解决方案是O(n^4),那么我错在哪里?谢谢!
我熟悉Big
对于第一个例子,这被证明是: O(n),尽管不确定为什么。
Example1:
for (k = 0; k <= n / 8; k++) // will be O(n/8) thus, O(n)
System.out.println(k); // will be O(n)
System.out.println("Hello World!"); // will be O(1) because not in a loop
for (p = n; p >= 1; p--) // will be O(n-1) thus, O(n)
System.out
public class foo{
public static void main(String[] args){
int a = 1;
int b = 1;
int n = 4;
//Focus is on the below for-loop
for(int x=1;x<=n;x++){
c=a+b;
}
}
}
x=1 -> O(1) //一个赋值语句
x<=n -> O(n+1
我现在正在研究算法,我遇到了一个例子,我作为一个Infinite loop回答,但在正确的答案中,它说它是O(log2n)。
function someFunc(n) {
for(var i = 0; i < n; i * 2) { // I think that Infinite loop cannot be O(log2n), can it?
console.log(i);
}
}
我在这里有点困惑。我不明白为什么,因为它和下面的Infinite loop一样,不是吗?
function loop(n) {
while(true) {
下面的示例循环的时间复杂度是O(n^2),谁能解释一下为什么是O(n^2)?因为它依赖于c的值。
循环1
for (int i = 1; i <=n; i += c)
{
for (int j = 1; j <=n; j += c)
{
// some O(1) expressions
}
}
循环2--
for (int i = n; i > 0; i -= c)
{
for (int j = i+1; j <=n; j += c)
{
// some O(1) expressions
我目前有以下伪代码,我正在尝试找出为什么这个问题的答案是O(n)。
sum = 0;
for (i = 0; i < n; i++) do
for (j = n/3;j < 2*n; j+= n/3) do
sum++;
我认为答案应该是O (n ^2),因为第一个for循环将运行'n‘次,第二个for循环将运行+= n/3,给它另一个(n除以某物的次数),这将简化为O(n^2)。有人能解释一下为什么是O(n)吗?
这个问题是为了复习过去的试卷,我只想知道我是否在正确的轨道上。
1. int i=1;
2. while (i <= n) {
3. for (int j=1; j<10; j++)
4. sum++;
5. i++;
6. }
7. for( int j = 1; j <= n; j++ )
8. for( int k = 1; k <= n; k=k*2 )
9. sum++;
( 1.)语句4执行了多少次?
A. O(n)
B. O(n^2)
C. O(原木)
D. O(n对数)
E.上述任何一项
我在这里选择了A
( 2.)语句
这样的问题可以在我很快写的考试中提出。我在一本书里找到了这个,但遗憾的是没有解决办法。所以我解决了它,我希望你能告诉我,如果我做得对?
a.)算法是计算什么的?
b.)基于n的算法运行时间分析
Input: Array A of length |A|=n with n >= 2
Output: Number x
x := 0;
for i := 1 to n do
for j := i+1 to n do
if x < |A[i] - A[j]| then
x := |A
此代码示例采用(N^2)的大O
results = []
for i in range(1000000)
result = [f(i)] + results
此代码示例采用(N)的大O
results = []
for i in range(1000000)
result = results + [f(i)]
为什么这两个算法的大O有如此明显的差异,唯一的区别是一个添加到列表的前面,另一个添加到列表的后面?
这也适用于Java吗?
很抱歉让你很痛苦。我知道这是经典的,我已经查过了,但我还是不明白为什么时间成本是O(n)。
这是我的密码。
def two_sum(L, sum):
targets = {}
for i in range(len(L)):
if L[i] in targets:
return (targets[L[i]], i)
else: targets[sum - L[i]] = i
虽然我知道L只被迭代一次,并且查找给定键的值是O(1),但是在dict O(n)中搜索一个实际的键不是吗?这不意味着,对于L中的每个值,都有一个O(n)
给出了n>1的fib(n)=fib(n-1)+fib(n-2),并给出了fib(0)=a,fib(1)=b ( a,b >0),下面哪个是正确的?
fib(n) is
Select one or more:
a. O(n^2)
b. O(2^n)
c. O((1-sqrt 5)/2)^n)
d. O(n)
e. Answer depends on a and b.
f. O((1+sqrt 5)/2)^n)
解决斐波纳契序列我知道:
fib(n)= 1/(sqrt 5) ((1+sqrt 5)/2)^n - 1/(sqrt 5) ((1-sqrt 5)/2)^n
但是,在这种情