标签: complexity-theory

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

NP,NP-Complete和NP-Hard有什么区别？

我知道网上有很多资源.我想阅读你的解释,原因是它们可能与那些不同,或者有些东西我不知道.

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

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

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

问题

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

在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

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

我想知道什么？ …

有人可以帮助解释如何构建堆是O(n)复杂性？

将项插入堆中O(log n),并且插入重复n/2次(其余为叶,并且不能违反堆属性).所以,这意味着复杂性应该是O(n log n),我想.

换句话说,对于我们"堆积"的每个项目,它有可能必须针对堆的每个级别过滤一次(这是log n级别).

我错过了什么？

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

有没有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序列的计算复杂度是多少以及如何计算？

len()Python内置函数的功能成本是多少？(列表/元组/串/字典)

我明天有一个计算机科学中期,我需要帮助确定这些递归函数的复杂性.我知道如何解决简单的案例,但我仍然在努力学习如何解决这些更难的案例.这些只是我无法弄清楚的一些示例问题.任何帮助将非常感谢,并将大大有助于我的学习,谢谢!

int recursiveFun1(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun1(n-1);
}

int recursiveFun2(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun2(n-5);
}

int recursiveFun3(int n)
{
    if (n <= 0)
        return 1;
    else
        return 1 + recursiveFun3(n/5);
}

void recursiveFun4(int n, int m, int o)
{
    if (n <= 0)
    {
        printf("%d, %d\n",m, o);
    }
    else
    {
        recursiveFun4(n-1, m+1, o);
        recursiveFun4(n-1, m, o+1);
    }
}

int recursiveFun5(int n)
{ …