标签: asymptotic-complexity

我在确定空间和时间的复杂性方面遇到了一些麻烦.例如,如果我的树具有分支因子b并且最多具有深度d,那么如何计算时间和空间复杂度？我知道它们是O(b ^ d)和O(bd),但我的问题是如何获得这些值.

谢谢!

有些人可以帮助我使用Big O(1)但不是Ω(1)的函数,反之亦然吗？一些解释会有很大帮助.

语句"算法A的最差情况运行时间"和"算法A的运行时间是否为O(n)"之间是否存在差异？

我认为"没有区别",因为最坏的情况是函数可以采用的峰值运行时间,O(n)意味着函数"受限".两者都有相同的含义.

希望我的逻辑是正确的.

这是什么表达˚F（Ñ）= 2 ^Ö（Ñ）平均，以精确的正式的方式？

是 3 ⁿ = O(2 ⁿ )？(3/2) ⁿ = O(2 ⁿ ) 怎么样？你能解释一下答案吗？

我第一次弄错了，无论你乘以 2 ⁿ的常数 C 是多少，3 ^{n 的}增长速度都比 2 ⁿ快。第二个也一样？

log(3 ⁿ ) = O(log (2 ⁿ )) 怎么样？我认为我们无法确定这一点，因为我们不知道日志的基础。

这是一个面试问题:

Given: f(n) = O(n)
       g(n) = O(n²)
find f(n) + g(n) and f(n)?g(n)?

这个问题的答案是什么？

我正在努力解决复发问题T(n) = T(n/8) + T(n/2) + T(n/4).

我认为首先尝试使用递归树方法,然后将其用作我对替换方法的猜测是个好主意.

对于树,因为在非叶级别没有工作,我认为我们可以忽略它,所以我试图在叶子的#上面提出一个上限,因为这是唯一相关的东西.

我认为树的高度是最长的路径T(n/2),它产生的高度为log2(n).那么我想树完成后,与各级充满(即我们有3T(n/2)),所以我们必须3^i在每一个级别的节点,所以n^(log2(3))离开.T(n)然后将O(n^log2(3)).

不幸的是,我认为这是一个不合理的上限,我想我已经让它有点太高了......关于如何解决这个问题的任何建议？

我有一个包含一年的矢量

Jan2013 Jan2013 Jan2013 Jan2014 Jan2014 Jan2014 Jan2014 Feb2014 Feb2014

基本上我想要做的是搜索向量,对于每个相同的记录,将它们组合在一起,例如

total count for Jan2013 = 3; 
total count for Jan2014 = 4; 
total count for Feb2014 = 2;

当然,正如我们所知,我们可以简单地编写多个if来解决它

        if(monthyear = "Jan2013")  {
            //add count   
        }

        if(monthyear = "Jan2014")  {
            //add count   
        }

        if(monthyear = "Feb2014")  {
            //add count   
        }

但是程序员不会以这种方式编写代码.如果2014年3月,2014年4月,2014年5月到2015年1月和2015年1月至2015年15月还有额外的月份.

从长远来看,我不认为我应该采用这种硬编码方法,并寻找更具动态性的方法.

我不是要求代码,而只是一些步骤,或许可以给我一些关于我应该研究什么样的c ++方法的提示.

提前致谢

O(n logstar(n))和O(n)之间是否存在真正的复杂性？我知道O(n sqrt(logstar(n)))和其他类似函数介于这两者之间,但我的意思是原始的,不是由logstar(n)组成的.

我得到了以下伪代码:

 j = 1
 while j < n:
      k = 2
      while k < n:
           k = k*k
      j++

在我的想法中,这段伪代码将具有以下复杂性:

 O(n*log(n))

由于外循环执行n次.虽然内循环基本上每次将增量步长分成两半.我的想法太远了吗？

编辑:1个以上(这些不是作业,我保证,只是要了解的例子)

 for i = 1 to n:
    for j = 1 to n:
       k = j*j
       while k < n:
          k++

在这种情况下,最外面的循环将执行n次.中间回路也将执行n次,把我们现在以n ²倍.最里面的循环,正如我所说,它将执行log(n)次,将我们放在O(n ²*log(n))次.我的理解是否正确？