将T（n）转换为Theta与地板

public static int myfun2(int n) { 
    int p, k, t; 
    p=n; 
    k=10; 

    while(p>=1){ 
     k=k+p; 
     for(t=n; t>=0; t=t-3){ 
      System.out.println(p + ", "+t); 
      k++; 

     } 
     p=p/3; 
    } 
    return k; 
}

以上是我必须执行分析的一些代码。我提出了公式（⌊log3（n）⌋+ 1）×（⌊n/3⌋+ 1）。这似乎是正确的答案。我遇到的问题是将其分配给更一般的Theta，如：Theta Choices 将T（n）转换为Theta与地板

这是第一次在分析中处理地板，所以我不知道他们对此有什么影响。我真的很感谢一些指导，为此找出Theta。

预先感谢您

来源

2016-09-22 feynmanium

试想地板造成。如果增加'n'，则执行时间基本上被量化为离散集合。但是，这并不会改变函数的整体行为（如果您愿意的话，它的精确度）。所以，只要忽略它们，就会产生复杂的'n log n'。 –

那么你会说在进行复杂度分析时，至少大部分时间的楼层可以被忽略吗？ – feynmanium

至少我想不出一个重要的例子。但这并不意味着它不存在。 –

在时间复杂度，你真的不关心常量，所以你有你的算法是Θ((⌊log3 (n)⌋+1) ×(⌊n/3⌋+1))这是简单Θ(nlog3(n)). 你也不在乎对数，因为log3中的基础（N）= C *的log（n），如此反复，因此正确答案是，你不要指望常量：

Θ(nlog(n)).

来源

2016-09-22 19:30:58 coder

将T（n）转换为Theta与地板

回答

相关问题