对于MakeMatrix,证明T(n)是O(n),S(n)是O(n^2),这创建了一个方阵,并且只将对角线元素设置为零。(忽略malloc的时间)
MakeMatrix(size):
A = malloc(size * size * sizeof(int))
for i from 0 to size -1
A[i,i] =0
return A
我想我理解为什么T(n)是线性的O(n),因为只有1个for循环,但是为什么空间复杂度是O(n^2)?
有人能解释一下为什么这是O(n log n)而不是O(n^2)吗?我的想法是,if语句是n times,else是log n,所以在这两种情况中,最坏的情况是O(n),所以将它与外部循环O(n)相乘,使之成为O(n^2),但显然是O(n log n),我不知道怎么做。
for i in range( len(nums_lst)):
if i < 10:
for k in range( len(nums_lst)):
print(nums_lst[0])
else:
j = 1
while j < len(nums_ls
有人能告诉我这个python函数的空间复杂性是什么吗?我相信是O(1),但我的朋友告诉我这是O(N)。
为什么他们说O(N):在for循环的每一次迭代中创建一个新的'a‘。
我为什么要说O(1):每次迭代和丢弃旧的“a”时,都会生成一个新的“a”。
def hello(n):
for i in range(n):
a = 10
如果这是伪码,空间复杂度会是一样的吗?
我有一个问题,我如何确定这个算法的复杂度?
int pow (int a, int b) {
int result=1;
while (b>0) {
result = result*a;
b = b-1;
}
return result;
}
void bar (int n) {
for (int i=0; i<pow(2,n); i++)
printf("%d", i);
}
教授的解决方案是,pow(a,b)具有O(n)的复杂度,并且由于for循环具有O(n)和O(2^n)的复杂度,因此最终bar
以下代码的时间复杂度是多少?
a = 2;
while (a <= n)
{
for (k=1; k <= n; k++)
{
b = n;
while (b > 1)
b = b / 2;
}
a = a * a * a;
}
--我在和外循环做斗争,,也就是loglogn,我不明白为什么。如果最后一行是a = a * a * a * a;,时间复杂度会发生什么变化?
for循环是O(n),内部循环是O(logn)。
所以总的来说,O(n*logn*loglogn)
以下代码的时间复杂度是多少?
def func(n):
for _ in range(n):
if n == 4:
for _ in range(n):
<do something>
对于一个特定的输入(n = 4),它将只是O(n^2),但对于所有其他输入,它将是O(n)。在这种情况下,最坏的情况显然是O(n^2),但我的讲师说O(n)是正确的答案。如果"big-Oh“符号表示的是最坏的情况,为什么它不是O(n^2)?
另一个是:
def func2(n):
for _ in rang
我手头有问题,可以通过以下两种方式解决。
if(...) //First if statement
for( i = 0; i < n; i++ ) //Loop over n elements
{ ... } //Some statement; Time Complexity O(1)
if(...) //Second if statement
for( i = 0; i < n; i++ ) //Loop over n elements
{ ... } //Some statement; Time Complexity
如果您转到leetcode.com/problems/find-the-duplicate-number/solution/ (问题287),会给出以下解决方案:
def findDuplicate(self, nums):
seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)
该解决方案的时间复杂度为O(n)。
我在试着弄清楚为什么会这样。我的想法是,如果你得到下面的列表:
x= 1,2,3,4,5,6,7,8,9,10,11,即数字
我正在尝试理解这个页面中的大O示例:
for (i = 0; i < N; i++) {
for (j = i+1; j < N; j++) {
sequence of statements }
}
我不明白为什么内部循环将运行在N if i=0上。如果是i=0,那么j=1,作为结果,内部循环的迭代次数应该是N-1。我理解为什么这个循环的复杂性是O(n^2)。我不明白的是,为什么内部循环以N的迭代次数开始,而不是N-1。
我是一个初级开发人员,仍然不是很熟悉大O。
这是我的leetcode问题的解决方案,我不确定这个解决方案的时间和空间复杂度是多少。
String s = "";
String t = "";
int back = 0;
for (int i = S.length() - 1; i >= 0; i--) {
if (S.charAt(i) == '#') {
back++;
continue;
}
if (back
我正在尝试设计一种算法来查找数组中两个相同元素的索引。输入是一个数组,输出是两个索引i&j,使得arrayi=arrayj。时间复杂度必须为O(nlogn)。
这是我尝试过的
let i=0 to size_of_array{
let j=i+1 to size_of_array{
if array[j]=array[i]{
print(i, j)
}
}
}
嵌套循环是O(n^2),但如果我尝试这样设计。时间复杂度是多少?
N是数组的大小,我的实现将运行O(n(n-1)+(n-2)+(n-3)....+1)次。它
我在思考如何正确计算这个函数的时间复杂度:
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)。
我说的对吗?
它只检查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;
这段代码是从破解编码采访书中得到的。
public static boolean isUniqueChars2(String str) {
boolean[] char_set = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) return false;
char_set[val] = true;
}
return true;
}
提交人提到,
时间
在“破解编码面试”一书中,第一个练习说“实现一个算法来确定一个字符串是否都具有唯一的字符(不使用额外的数据结构)”。解决方案是: public static boolean isUniqueChars(String str) {
boolean [] char_set = new boolean[256];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) return false;
char_set[v
我需要帮助的问题是:
for (int i = 0; i < n*n; i++)
for (int j = 0; j < n*n; j++)
if (i == j)
for(int k = 0; k < n; k++)
sum++;
我理解i和j循环是如何O(n^4)的。但是,从if语句开始,我不知道剩余代码片段的大O是什么。如果我在课堂上正确地复制了答案,O(n^4)就是整个代码片段的运行时间。因此,从if开始的运行时间似乎可以忽略不计。尽管如此,我仍然想了解它是什么,以及为什么我认为答案是O(
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
int left = getHeight(root.left);
int right = getHeight(root.right);
if (Math.abs(left - right) > 1) return false;
return isBalanced(root.left) && isBalanced(root.right);
}
private int getHeigh
如果循环变量除以/乘以一个常量,为什么我们认为时间复杂度为O(Logn)?喜欢,
for (int i = 1; i <=n; i *= c) {
// some O(1) expressions
}
for (int i = n; i > 0; i /= c) {
// some O(1) expressions
}
我们有以下伪代码
Input: An array A storing n ≥ 1 integers.
Output: The sum of the elements in A.
s←A[0]
for i←1 to n−1 do
s←s+A[i]
return s
首先,我一直在伪代码中注意到这一点,为什么我们要写for i←1 to n−1 do,而不是i←1 to n do或for i←1 to n+1 do呢?
其次,它的复杂度是O(n-1),所以O(n)..I理解它为什么是O(n),这是我看到代码时所想的,但为什么一开始是O(n-1)呢?
编辑:我想知道的是我们是如何得到O(n-1)的
我在网上找到了这个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
偶然发现了一个计算数字平方根的(可怕的)算法。关于时间复杂度发生了一场小争论。我断言时间复杂度是O(n^2),因为对于n个输入,它将被乘以n倍。我的朋友断言时间复杂度实际上是O(n)。谁是对的?为什么?
def squareRoot(x):
if x<0:
return "undefined"
elif x==0:
return 0
for i in range(0,x):
if(i*i)==x:
return i