这段代码是为了求Fibonacci序列中偶数的和。我只想知道这个程序的时间复杂性
int sum = 2;
int a = 1;
int b = 2;
while (a < 4000000) {
int c = a;
a = b;
b = c + b;
if (b % 2 == 0) {
sum += b;
}
}
System.out.println(sum);
如果我也能得到一个解释,我会很感激的。
我认为这段代码的时间复杂度将是O(n^2),但我不确定,所以如果有人能解释一下这段代码的时间复杂度,那将是非常有帮助的 int func2()
{
int i, j, k = 0;
scanf("%d", &n);
for (i = 1; i < n; i++)
{
i -= 1;
i *= 2;
k = k + i;
for (j = 1; j < n; j++);
}
}
我在班上做了一次测验,但成绩不是很好。我想知道是否有人可以向我解释我在这里做错了什么--我们的教授因为我们搬到网上而被办公时间淹没了,所以我想我应该在这里发帖。 def functionA(n):
level = n
total = 0
while level > 1:
for i in range(0,n):
level = level // 2
total = total + i
return total 我的答案是:上面的函数是O(log ),因为for循环在每次迭代中将级别变量一分
function longestPalindromicSubstring(str) {
let longest = '';
for ( let i = 0; i < str.length; i++) {
let word1 = palindromeFinder(str, i, i );
let word2 = palindromeFinder(str, i, i+1);
longest = [ word1, word2, longest ].reduce( (long, word) => long
有人能告诉我这个python函数的空间复杂性是什么吗?我相信是O(1),但我的朋友告诉我这是O(N)。
为什么他们说O(N):在for循环的每一次迭代中创建一个新的'a‘。
我为什么要说O(1):每次迭代和丢弃旧的“a”时,都会生成一个新的“a”。
def hello(n):
for i in range(n):
a = 10
如果这是伪码,空间复杂度会是一样的吗?
我想确定second_max函数的复杂性,但是我如何做,如何确定我的代码和其他代码的时间复杂度
from random import randint
import sys
from bigO import BigO
def r_array(r_i= 0,r_e = 100,step=10):
return [randint(r_i, r_e) for i in range(r_i, r_e, step)]
def second_max(arr):
n_max = -sys.maxsize
n_s_max = -sys.maxsize
for i in ra
def sort_list(lst):
result = []
result.append(lst[0])
for i in range(1,len(lst)):
insert_list(lst[i], result)
return result
def insert_list(x, lst):
a = search(x, lst)
lst.insert(a, x)
return lst
def search(x, seq):
for i in seq:
if x<i:
这是我的第一个问题,我很确定我也会收到我的第一个答案:
我必须对一个算法进行渐近分析,该算法从一个数组A[1...n]计算一个矩阵M[n][n],该矩阵包含每个M[i][j]的一个值,由下式给出:
M[i][j] = (A[i] + ... + A[j])/(j-i+1), if i<=j
和
M[i][j] = 0, if i>j
for i=1 to N do [N]
for j=1 to N do [N]
if(i<=j) [cost]
start=i
准备考试。我认为时间复杂度是O(n^2),空间复杂度是O(1)。请帮帮忙,我说的对吗? public static String lastSubstring(String s) {
int start=0;
int end = start+1;
int len =0;
while (end + len < s.length()) {
if (s.charAt(start + len) == s.charAt(end + len)) {
len++;
} else if (s.c
如果求f(n)是θ(N)
i = 1;
sum = 0;
while (i <= n)
do if (f(i) > k)
then sum += f(i);
i = 2*i;
它的运行时间是O(n^3),因为函数可能被调用了n次,还是它是O(n)?或者是关于θ的东西,因为这是我们所知道的信息?我对此非常迷茫.
我有以下代码,并试图找出它的时间复杂性:
int sum(int m, int n, int K) {
int s = 0;
for (int i = 0; i < n; i++) {
s += i;
if (i == K % 2) {
for (int j = 0; j < m; j++) {
s += j;
}
}
}
return s;
}
根据代码,外循环在O(n)处运行,内环在O(m)处运行。但是,内部循环只执行一
这些循环的时间复杂度是多少?如果我错了,请纠正我。
这个循环是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
}
}
下面的函数的时间复杂度/增长顺序是什么?
def multiply(a, b):
'''Takes two integers and computes their product.'''
res = 0
for i in range(1, b+1):
res += a
return res
我知道b的大小是线性的,但是a的大小呢?
谢谢!
我试图开发一种解决方案,将O(n^2)或O(n*m)算法的时间复杂度降低为O(n)或O(n+m)算法。例如:
let arr = [[1, 2], [1, 2, 3], [1, 2, 3, 4, 5, 6, 7, 8]];
let x = 0;
let len = getArrayMaxLength (arr) //Get the maximum length of a 2d array which in this example is 8.
for (let i = 0; i < len && x < arr.length; ++i
我必须分析这个循环和其他循环,并使用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
现在我
我的任务是编写一个返回自制链接列表长度的方法。该方法必须是在恒定时间O(1)。我的想法是将计数器增加1,总是链接列表中的节点不为null,而且一点也不影响列表的大小,以避免O(n)。
我的代码:
public int getLength() {
// TODO Code hier einfügen
if (headNode == null) {
return 0;
}
int count = 0;
while (headNode != null)
{
count++;
headNod
我已经看到,在大多数情况下,时间复杂性与空间复杂性有关,反之亦然。例如,在数组遍历中:
for i=1 to length(v)
print (v[i])
endfor
这里很容易看出算法的时间复杂度是O(n),但在我看来,空间复杂度也是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
很明显,一个while (i < k)将运行k个项目--或者不运行,这取决于i的起始值。 但是如果我有一个while循环,比如: while (counter != k && !found) {
if (some condition)
found = true;
else
counter++;
} 如果我不知道何时找到将被设置为真,我如何计算最坏情况的时间复杂度?
let array = [1,7,2,2,3,7,4];
while(array.length){
// get last item
let item = array.pop()
// remove duplicates
const filteredArray = array.filter(content => content!==item);
// if filteredArray had duplicate items then log the ite
有一个问题要求返回数组元素的所有唯一三重奏,这些元素加起来等于零(交换两个元素在三胞胎中的位置不算唯一)。
我想出了以下代码:
function threeSum(nums) {
nums.sort((a, b) => a - b);
const result = [];
for (let i = 0; i < nums.length; i++) {
// skipping duplicates
if (i !== 0 && nums[i] === nums[i - 1]) continue;
let left = i + 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
这是一个用于在一维数组中查找连续子数组的最大和的程序。 int maxSubArraySum(int a[], int size)
{
int max_so_far = 0, max_ending_here = 0;
for (int i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if (max_ending_here < 0)
max_ending_here = 0;
/* Do not com