标签: big-o

我更喜欢尽可能少的正式定义和简单的数学.

我目前正在学习Big O Notation运行时间和摊销时间.我理解O(n)线性时间的概念,意味着输入的大小成比例地影响算法的增长...例如,二次时间O(n ²)等也是如此.即使算法也是如此. ,例如置换生成器,具有O(n!)倍,通过阶乘生长.

例如,以下函数是O(n),因为算法与其输入n成比例增长:

f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}

同样,如果有嵌套循环,则时间为O(n ²).

但究竟什么是O(log n)？例如,说完整二叉树的高度是O(log n)是什么意思？

我知道(可能不是非常详细)什么是对数,在这个意义上:log ₁₀ 100 = 2,但我无法理解如何识别具有对数时间的函数.

大多数拥有CS学位的人肯定会知道Big O代表什么.它可以帮助我们衡量算法的实际效率(如何),如果你知道你试图解决的问题属于哪个类别,你可以弄清楚是否仍然可以挤出那么少的额外性能.¹

但我很好奇,你如何计算或近似算法的复杂性？

¹ _{但正如他们所说,不要过度,过早优化是所有邪恶的根源,没有正当理由的优化也应该得到这个名称.}

有时我看到Θ(n)带有奇怪的Θ符号,中间有一些东西,有时只有O(n).这只是打字的懒惰,因为没有人知道如何输入这个符号,或者它是否意味着不同的东西？

在讨论算法的时间复杂度时,"恒定摊还时间"是什么意思？

在使用PHP一段时间后,我注意到并非所有PHP内置函数都如预期的那样快.考虑下面两个可能的函数实现,它使用缓存的素数数组来查找数字是否为素数.

//very slow for large $prime_array
$prime_array = array( 2, 3, 5, 7, 11, 13, .... 104729, ... );
$result_array = array();
foreach( $prime_array => $number ) {
    $result_array[$number] = in_array( $number, $large_prime_array );
}

//speed is much less dependent on size of $prime_array, and runs much faster.
$prime_array => array( 2 => NULL, 3 => NULL, 5 => NULL, 7 => NULL,
                       11 => NULL, 13 => NULL, .... 104729 => NULL, ... );
foreach( $prime_array => $number ) …

有没有O(1/n)算法？

或者其他任何小于O(1)的东西？

我理解Big-O表示法,但我不知道如何为许多函数计算它.特别是,我一直试图弄清楚Fibonacci序列的幼稚版本的计算复杂性:

int Fibonacci(int n)
{
    if (n <= 1)
        return n;
    else
        return Fibonacci(n - 1) + Fibonacci(n - 2);
}

Fibonacci序列的计算复杂度是多少以及如何计算？

我问的更多关于这对我的代码意味着什么.我在数学上理解这些概念,我只是很难在概念上围绕它们的意思.例如,如果要对数据结构执行O(1)操作,我理解它必须执行的操作量不会增加,因为有更多项.而O(n)操作意味着您将对每个元素执行一组操作.有人可以在这里填空吗？

• 就像O(n ^ 2)操作究竟会做什么一样？
• 如果一个操作是O(n log(n)),这意味着什么呢？
• 有人必须抽烟才能写出O(x!)？

Big-O表示法O(n)和Little-O表示法有o(n)什么区别？