給定代碼的時間複雜度

-2

有人可以告訴我下圖代碼的複雜性。給定代碼的時間複雜度

std::cin>>n1; 
    int ctr=0; 
    for(int i=2;i<=n1;i++) 
    { 
     if(i>=n/2&&ctr==0) 
     { 
     cout << " You entered a prime no"; 
     break; 
     } 
    else if(n1%i==0) 
     { 
     ctr++; 
     cout<<i<<" "; 
     n1/=i; 
     } 
}

有人可以建議如何計算這種循環涉及多個if-else條件的複雜性嗎？

來源

2014-02-12 user3250183

你的循環是'O（infinity）' – TemplateRex

是的，for循環是O（1）。多個if-else條件會在做什麼？ – Beta

@RikayanBandyopadhyay這是什麼褻瀆？ –

內環是O(1)。外循環的複雜性取決於代碼與n的作用，並且您沒有顯示代碼，所以它可能是任何東西。

對於一般指導原則：漸近複雜度總是與數量有關。通常情況下，這被認爲是輸入大小（無論解決問題的手段是什麼），並表示爲n。在你的情況下，它很可能是變量n，因爲它用於循環停止條件。

一旦你知道你想要複雜性的數量（n），這很簡單。不依賴於n的操作是O(1)。對n的每個值做O(f)工作量的操作是O(n * f)，其中f確實可以是n的函數。它遞歸更棘手，但這是基本的概述。

來源

2014-02-12 14:56:04 Angew

談論內循環 - 如果它不是i <= 9而是i <= n，那麼這個變量就是O（n）正確嗎？ – Bloodcount

@Bloodcount是的（至少在身體不會修改'n'的情況下）。在OP的更新情況下，我不得不考慮該部門是否足以將其減少到'O（log（n））'。 – Angew

int n; 
std::cin >> n; 

// O(oo) e.g. O(infinite) 
while(n > 0) { 
    // for loop is O(1) 
    for(int i = 1 ; i <= 9 ; i++) { 
     if(n % i == 0) { 
      //piece of code involving O(1)complexity. 
     } 
    } 
    // this makes the while loop O(1) 
    if (n == 10000000000000) { 
     break; 
    } 
}

該算法是O（1）

來源

2014-02-12 14:55:52

因此你可以用零除？ –

不好意思？你是什麼意思？我不認爲我可以除以零;） –

哈哈，n％我當我= 0除以0. –

的for循環的複雜性是O(n)其中n是迭代次數...

這裏n=9，但它是錯誤採取的結論，即在一般循環是穩定的（O(1)）和不相關到迭代次數

來源

2014-02-12 14:58:46 apomene

給定代碼的時間複雜度

回答

相關問題