相关疑难解决方法(0)

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

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

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

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

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

我真的很困惑大O,大欧米茄和大Theta符号之间的差异.

我知道大O是上界,大欧米茄是下界,但大Ө(theta)究竟代表什么？

我读过它意味着紧张,但这意味着什么？

我正在学习使用YouTube编程和我能找到的任何内容.我偶然发现了一些Big O问题,我对其中一个问题感到很困惑.

for (int i = 0; i < n; i++)
    for (int j = 0; j < 2; j++)
        cout << i << " " << j << endl;

我的第一个想法是它是O(n ²),因为有2个for循环.然后我仔细看了一下,注意到内部for循环只从0到2.

根据我的理解,Big O着眼于最糟糕的情况.我的想法是,如果n = 2那时它会导致O(n ²)但是所有其他情况都会导致O(n),这真的让我感到困惑.

有人可以解释为什么这是O(n ²)或O(n)？

这里有很多关于SO的相关问题,但他们都要求编写一个程序来计算任意算法的复杂性(这显然是不可判定的).我愿意对输入做出以下限制:

1. 算法终止
2. 该算法纯粹是功能性的

问题是,是否可以编写程序来通过静态分析来计算这种算法的时间复杂度？如果输入算法未终止,则程序行为未定义(可能会崩溃,返回谎言或无法终止).