相关疑难解决方法(0)

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

问题

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

在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

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

我想知道什么？ …

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

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

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

在这个答案的参考下,什么是Theta(紧束缚)？

Omega是下限,很明白,算法可能需要的最短时间.我们知道Big-O代表上限,意味着算法可能需要的最长时间.但我不知道Theta.

开始研究复杂性,我正在努力解决这个问题:

void what(int n) {
    int i;
    for (i = 1; i <= n; i++) {
        int x = n;
        while (x > 0)
            x -= i;
    }
}

好吧,第一个循环显然是O(n).第一次迭代是O(n),第二次是O(n/2)..而且就像log(n)我猜的那样？这意味着O(n) * O(log(n)) = O(n * log(n)) complexity.我做对了吗？

编辑:(不是重复)我知道Big O是什么.我已经在特定情况下询问了正确的评估.

我最近在我的大学开设了数据压缩课程.但是,我发现使用术语"熵",因为它适用于计算机科学而不是模棱两可.据我所知,它大致转化为系统或结构的"随机性".

计算机科学"熵"的正确定义是什么？

什么是大O符号？你用它吗？

我猜错了这个大学课:D

有没有人使用它并给出一些他们使用它的真实例子？

也可以看看:

8岁儿童的大O？
大O,你如何计算/近似它？
您是否在现实生活中应用了计算复杂性理论？

我知道有很多关于大O符号的问题,我已经检查过了:

• 大O的简单英语解释
• 大O,你如何计算/近似它？
• Big O表示法作业 - 代码片段算法分析？

仅举几例.

我知道的"直觉"如何计算它n,n^2,n!等等,但是我完全失去了关于如何计算它是算法log n,n log n,n log log n等等.

我的意思是,我知道Quick Sort n log n(平均)..但是,为什么？合并/梳子等同样的事情

任何人都可以用不太算数的方式解释我,你怎么计算这个？

主要原因是我即将进行大型采访,我很确定他们会要求这种东西.我已经研究了几天了,似乎每个人都有解释为什么冒泡排序是n ^ 2或维基百科上不可读的解释(对我而言)

有人能给我一个具有平方根(n)时间复杂度的算法的例子.平方根时间复杂度甚至意味着什么？

在寻找与"大O"符号相关的答案时,我已经看到了许多SO答案,例如这个,这个或者这个,但我仍然没有清楚地理解一些观点.

为什么我们忽略了效率？

例如,这个答案说最终的复杂性2N + 2是O(N); 我们也删除了领先2的系数和最终的常数2.

删除2可能可以理解的最终常量.毕竟,N可能会非常大,因此"遗忘"决赛2可能只会将总比例改变一小部分.

但是,我无法清楚地了解如何消除领先的系数并没有产生影响.如果2上面的领先成为a 1或a 3,则对总计的百分比变化将很大.

同样,显然2N^3 + 99N^2 + 500是O(N^3).我们如何忽视99N^2它500？