將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與地板

回答

相關問題