标签: time-complexity

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

找出JavaScript数组是否包含对象的最简洁有效的方法是什么？

这是我知道的唯一方法:

function contains(a, obj) {
    for (var i = 0; i < a.length; i++) {
        if (a[i] === obj) {
            return true;
        }
    }
    return false;
}

有没有更好,更简洁的方法来实现这一目标？

这与Stack Overflow问题密切相关问题在JavaScript数组中查找项目的最佳方法是什么？它使用的方法寻找数组中的对象indexOf.

我目前正在学习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,但我无法理解如何识别具有对数时间的函数.

项目欧拉和其他编码竞赛通常有最长的运行时间或人们吹嘘他们的特定解决方案运行的速度.使用python,有时候这些方法有点像kludgey - 即添加时间码__main__.

分析python程序运行多长时间的好方法是什么？

问题

如何找到算法的时间复杂度？

在SO上发布问题之前我做了什么？

我走过了这个,这和许多其他链接

但是,我没有能够找到关于如何计算时间复杂度的明确而直接的解释.

我知道什么 ？

假设代码如下所示:

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

说一个像下面这样的循环:

for (int i = 0; i < N; i++) {        
    Console.Write('Hello World !');
}

int i = 0; 这只会执行一次.实际计算时间i=0而不是声明.

我<N; 这将执行N + 1次

i ++; 这将被执行N次

所以这个循环所需的操作数量是

{1+(N + 1)+ N} = 2N + 2

注意:这仍然可能是错误的,因为我对计算时间复杂度的理解没有信心

我想知道什么？ …

鉴于字符串在.NET中是不可变的,我想知道为什么它们被设计为string.Substring()需要O(substring.Length)时间,而不是O(1)？

即,有什么权衡,如果有的话？

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

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

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

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

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

在任何情况下,您是否更喜欢O(log n)时间复杂度和O(1)时间复杂度？或O(n)到O(log n)？

你有什么例子吗？