标签: asymptotic-complexity

如果我有一个需要4n ^ 2 + 7n动作才能完成的算法,它的O是什么？O(4N ^ 2)？为O(n ^ 2)？

我知道7n被切断,但我不知道是否应该保留n ^ 2系数.

谢谢

public void foo(int n, int m) {
    int i = m;

    while (i > 100) {
        i = i / 3;
    }
    for (int k = i ; k >= 0; k--) {
        for (int j = 1; j < n; j *= 2) {
            System.out.print(k + "\t" + j);
        }
        System.out.println();
    }
}

我认为复杂性将是O(logn).
这是内循环的产物,外循环 - 永远不会执行超过100次,因此可以省略.

我不确定的是while子句,它是否应该被整合到Big-O复杂性中？对于非常大的i值,它可能产生影响,或算术运算,无关紧要,算作基本操作,可以省略？

我正在研究随机快速排序算法.我意识到这个算法的运行时间总是表示为"预期运行时间".

指定或使用"预期运行时间"的原因是什么？我们为什么不计算最差或平均情况？

假设我们有一个包含n个元素的二进制堆,并希望插入n个更多的元素(不一定是一个接一个).这需要的总时间是多少？

我认为这是theta(n logn),因为一次插入需要登录.

我试图找出使用Big O表示法的for循环的复杂性.我之前在其他课程中已经完成了这个,但是这个比其他课程更严格,因为它是在实际的算法上.代码如下:

for(cnt = 0, i=1; i<=n; i++) //for any size n
{
    for(j = 1; j <= i; j++)
    {
       cnt++;
    }
}

和

for(cnt = 0, i=1; i<=n; i*=2) //for any size n
{
    for(j = 1; j <= i; j++)
    {
       cnt++;
    }
}

我已经到了,第一个循环具有O(n)复杂性,因为它经过n次列表.至于第二个循环,我有点迷失.我相信,对于每个被测试的n,它都会经历一次循环.我(错误地)假设这意味着每次评估循环都是O(n*i).在我的假设中是否有任何我遗漏的东西.我知道cnt ++是恒定的时间.

感谢您在分析中提供的帮助.每个循环都在自己的空间中,它们不在一起.

我想计算这个嵌套for循环的θ复杂度:

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < j; k++) {
                // statement

我会说它是n ^ 3,但我不认为这是正确的,因为每个for循环不会从1变为n.我做了一些测试:

n = 5 - > 10

10 - > 120

30 - > 4060

50 - > 19600

所以它必须在n ^ 2和n ^ 3之间.我尝试了总和公式等,但我的结果太高了.虽然n ^ 2 log(n),但那也错了......

假设我正在打印一个字符串,如下所示:

printf("%s", s);

我们可以假设这个函数的渐近复杂性是什么？

它是O(n),其中n是strlen(s) - 它的长度是多少？或者它是某种方式O(1),恒定的时间.或者不同的东西？不过,我认为你需要知道printf是如何实现的.任何见解都表示赞赏!

(我应该澄清一点,我说的是C而不是C++,但我怀疑它们的实现方式不同)

编辑:将格式字符串添加到printf()

我想了解如何达到下面递归关系的复杂性.

T(n) = T(n-1) + T(n-2) + C 鉴于T(1) = C和T(2) = 2C;

通常对于像T(n) = 2T(n/2) + C(给定T(1)= C)的方程式,我使用以下方法.

T(n) = 2T(n/2) + C
=> T(n) = 4T(n/4) + 3C
=> T(n) = 8T(n/8) + 7C
=> ...
=> T(n) = 2^k T (n/2^k) + (2^k - 1) c

现在什么时候n/2^k = 1 => K = log (n)(到基地2)

T(n) = n T(1) + (n-1)C
     = (2n -1) C
     = O(n)

但是,我无法针对我所遇到的问题提出类似的方法.如果我的方法不正确,请纠正我.

是2 ^ n =Θ(4 ^ n)？

我很确定2 ^ n不在Ω(4 ^ n)中,因此不在Θ(4 ^ n)中,但我的大学导师说它是.这让我很困惑,我找不到每个Google的明确答案.

它说的是一个O(1)操作的例子是,在一个数组访问的元素.根据一个来源,O(1)可以通过以下方式定义:

[Big-O of 1]表示算法的执行时间不依赖于输入的大小.它的执行时间是不变的.

但是,如果想要访问数组中的元素,操作的效率是否取决于数组中的元素数量？例如

int[] arr = new int[1000000];
addElements(arr, 1000000); //A function which adds 1 million arbitrary integers to the array. 

int foo = arr[55]; 

我不明白最后一个语句如何描述为在O(1)中运行; 数组中的1,000,000个元素是否与运行的运行时间有关？当然,找到元素55需要的时间比元素1要长？如果有的话,这对我来说就像O(n).

我确定我的推理存在缺陷,但是,我只想澄清一下如何在O(1)中运行？