我有一个学校作业,我需要确定两个函数的大O符号。问题是我们还没有真正的Big O课程,更不用说Python了。有人能解释一下如何确定大O,给定这些函数吗?谢谢!
def my_func1(inputs):
n = len(inputs)
result = 0
for i in range(n):
j = 1
while j < n:
result += inputs[i] * inputs[j]
j *= 2
return result
def my_func2(inputs
为什么每个语句的下面的代码引用大O常数(这里我使用1作为约定)?
我的意思是,如果数组的大小越大,时间复杂度就会越大,对吗?而且,总人数会越来越大,这会影响到复杂性吗?
伪码
def find_sum(given_array)
total = 0 # refers to O(1)
for each i in given array: #O(1)
total+=i #O(1)
return total #O(1)
我只是在学习大O符号,我对嵌套循环感到困惑:
for (int x = 0; x < n; x++)
for (int y = 0; y < n; y++)
for (int z = 0; z < y; z++)
anything();
据我所知,上面的内部循环执行n(n+1)/2次,第二个循环执行n次,第一个循环执行n次。这不是意味着大O是n x n x n(n+1)/2 = O(n^4)吗?为什么第二个循环没有包含在大O公式中?
我知道,如果我有一个for循环和一个嵌套的for循环,这两个循环都迭代1 to n次数,我可以将两个循环的运行时间乘以得到O(n^2)。这是一个干净而简单的计算。但是,如果有这样的迭代,
n = 2, k = 5
n = 3, k = 9
n = 4, k = 14
其中k是内部for循环迭代的次数。在某一点上,它比n^2大,然后它就是n^2,然后它变得比n^2小。假设你不能基于k确定n,甚至可能n的这些点相距很远,那么如何计算大O呢?
我试过作图点。在某种程度上,我可以说它是O(n^3),因为有些点超过了n^2,再往下看,就是O(n^2)。我该选哪一个?
func(p)的大O时间复杂度是多少?C++代码如下。
int get_power(int a, int b)
{
if(!b) return 1;
if(b%2) return a * get_power(a, b/2);
return get_power(a, b/2);
}
int func(int p)
{
int sum = 0;
for(int i = 1; i <= p; ++i)
{
sum += get_power(i, 5);
}
return sum;
}
int main()
{
int c;
有没有人能帮我找出这两个函数的大O:
int sum(int A[], int i, int n) {
if (n == 1)
return A[i];
return sum(A, i, n/2) + sum(A, i + n/2, (n+1)/2);
}
以及的“排序”函数:
void swap(int& a, int& b) {
int temp = a;
a = b;
b = temp;
}
void swapMin(int A[], const int& index) {
int indexMin
我们学习了大O符号,但我也经常看到T(n)。例如,
public static Comparable[] mergeSort(Comparable[] A, int low, int high) {
if (low < high) { //at least 2 elements? //cost = c
int mid = (low + high)/2; //cost = d
Comparable[] A1 = mergeSort(A, low, mid); /
我必须找到以下函数的运行时间。
S=0
For i=4 to n^2
For j=5 to 3*i*log(i)
S=S+i-j
Return S
到目前为止,我相信运行时间是T(n)=((n^2)-3)*(3*i*log(i)-4),但我不能从n的角度得到第二部分。我还计算出它的最大值或大的O表示法是((n^2)-3)(3(n^2)*log(n^2)),即如果n^2是通过内部循环的每一次迭代的i的值,但情况并非如此,这基本上告诉我它可以写成O((n^4)*log(n^2)).为了计算出较大的θ值,我一直试图为3*i*log(i)计算一个平均值,作为每次迭代的i
我希望遍历列表中的第三个元素。但是,考虑到大O表示法,大O复杂度是O(n),其中n是列表中的元素数,还是O(n/3)是第三个元素?
换句话说,即使我指定列表应该只对第三个元素进行迭代,Python是否仍在遍历整个列表?
示例代码:
def function(lst):
#iterating over every third list
for i in lst[2::3]:
pass
假设我们有以下两个函数:
def is_prime(x):
"""Take an integer greater than 1 and check if it is a prime number."""
for i in range(2, int(x**0.5) + 1):
if x % i == 0:
return False
return True
def multiply(a, b):
"""Take two integers and comp
作为完全自学(和StackOverflow)的人,我是大O符号的新手,需要在即将到来的一些面试中更好地理解它。 我的问题是,当复杂度低于N时,如何在Big-O中进行注释?一个例子是质数计算器,它检查直到N/2的每个整数的余数,因为如果我们发现没有小于一半的除数,可以肯定上半部分也不会有。 那么,就符号而言,这是O(N/2),还是N变成了N = N/2? def primecheck(num):
i = 2
while i <= ( num // 2 ):
if not (num % i):
return False
i += 1
return T