试图将我的注意力集中在大的O符号和时间复杂度上,发现如果语句对时间复杂性的影响是如何的,那么很难理解。
在下面的函数中,if语句中的操作将只运行一次,因为只有当binarySearch为输入返回true时,它才会进入If操作。
但是if语句将执行O( n )次,使用的是binarySearch (日志n)。
这里的时间复杂度是O(n)还是O(n*logn)?想要得到正确答案的解释,因为我很难理解if语句的log比较是如何影响方法的时间复杂性的。
public static boolean what2 (int [][] m, int val)
{
for (int i = 0; i &
如果我们的algo输入是一个大小为n的数组A,我们必须将它复制到另一个数组B中。
什么是最坏的情况下的空间效率在θn表示法这个阿尔戈?
我相信在大O表示法中最坏的情况是O(nlogM),其中n是数组A中的元素数,logM是以位为单位的最大整数占用的空间。但我不知道在θ表示法中最坏的情况下的空间效率。
我认为应该是: Theta(求和i=1 to n (logni))
其中logni是数组A的第一个索引处的整数占用的空间。
我有两个数组
a of length n
b of length m
现在,我想找到这两个数组共有的所有元素。
算法
构建由A的所有元素组成的散列映射
现在,对于B中的每个元素x,检查元素x是否存在于hashmap中。
分析总体时间复杂度
用于构建hashmap O(n) 的第二步复杂度为O(m)
所以总体上是O(m+n)。我说得对吗?
什么是O(m+n) =?什么时候m大,反之亦然?
我正在学习大O符号,我需要帮助来理解以下程序的大O符号是如何派生的: static void myMethod(int[] arr, in t)
{
for (int i = 0; i < n - 1; i++)
{
int variable = nextMethod(inputArray, i, n - 1);
int temp = inputArray[i];
inputArray[i] = inputArray[variable];
inputArray[variable] = temp;
}
}
static int nextMet
我正在学习大O符号,我想找到我从Project Euler中解决的一个数学问题的大O符号。
total
for x (0..9){
for y (0..9){
for z(0..9){
if(some_condition == true){
total = total + permute(x,y,z)
}
}
} }
print total
我的猜测是O(N^3),因为有3个循环,但我不确定
我想弄清楚这段代码的大O复杂度: prime_factorize(N) {
for (int i = 2; i <= N; i++) {
while (N % i == 0) {
print i
N = N / i
}
}
} 这实际上不是一种编程语言--它只是伪代码。 我知道伪代码在做什么。我也知道代码可以优化为只到sqrt(N),但我想在发布代码时弄清楚代码的运行时。 虽然很容易说运行时是二次的,但我非常确定这是错误的。我之所以认为它是错误的,是因为我知道质数筛分算法是在O(nloglogn)
我很难弄清楚这段代码的大o符号运行时间。我会认为它是O(n),因为i=0和第一个while循环一直运行到i=n,然后第二个while循环进入,整个循环都把我抛到一边。
i=0
sum = 0;
while i<n:
sum++
if i==3 or i==7 or i==5:
j=0
while j<n:
sum++
j++
i++
我编写了一段代码,用于查找未排序数组的中值。这代码的大O是什么?你能解释一下吗?我们能优化运行时的复杂性吗?
public static int medianElement(int[] array,int low, int high) {
int[] tmpArray = new int[high - low + 1];
for (int i = 0; i < high - low; i++) {
tmpArray[i] = array[low + i];
}
boolean changed = true;
while (chan
你好,我使用大O符号已经有一段时间了,所以我有点生疏了。
我知道有一个循环,循环n次是O(n),在另一个循环n次的循环中有一个循环n次是O(n^2)。
但是在下面的代码片段中,我有一个循环n次,在这个循环中,n-i次循环。
对于这段代码,最坏的和最好的O符号是什么?
最糟糕的是它在没有找到碰撞的情况下运行,而最好的情况是前两个矩形之间有拼接。
class TestClass
{
bool Run(List<Rectangle> R)
{
var b = false;
var i = 0;
var n = R.Count
我试着理解“大O”,并认为通过一个简单的程序可能会有所帮助。
def sum(n):
k = 0
j = 0
while k < n:
k = k + 1
while j < n:
j = j + 1
k = k + j
return k
首先给K和j赋值0,值为2次,第一次which循环执行1次赋值n次,第2次执行2次赋值n次。表达式为2+n+ 2n。
由于上述表达式(2和n)中的前两个项是常数,因此与第三个项相比,它们将变得无关紧要,后者是n随n的增长而乘以2的第三项。所以代码的大O是O(2