O（n * log n）工作，然後O（n^2）工作的代碼的複雜性是什麼？

-1

我有一個算法，首先在O(n*log(n))時間做一些事情，然後在O(n^2)時間做其他事情。我是正確的總的複雜性將是O（n * log n）工作，然後O（n^2）工作的代碼的複雜性是什麼？

O(n*log(n) + n^2) 
= O(n*(log(n) + n)) 
= O(n^2)

因爲log(n) + n由+ n主導？

這是正確的，n²項將佔主導地位。 –

該聲明正確無誤，因爲O(n log n)是O(n^2)的子集;然而，正式的證明將包括選擇和構造適當的常數。

2017-04-05 14:23:37 Codor

如果兩者的通話概率相等，那麼你是對的。但是，如果兩者的概率不相等，則必須進行攤銷分析，將罕見的昂貴呼叫（n²）分配給多個快速呼叫（n log（n））。對於快速排序（例如，通常需要n log（n），但需要n 2），您可以證明由於攤銷分析的結果，平均運行時間爲n log（n）。

2017-04-05 16:50:09 gartenkralle

我想你已經誤解了這個問題。我認爲它是關於一個由兩個步驟組成的算法：一個運行在O（n log n）時間，後面是一個以O（n 2）運行的時間。沒有涉及的可能性。 – ruakh

那麼codor的答案是最好的 – gartenkralle

複雜性分析規則之一是您必須刪除指數較低或較低的因子。

nlogn vs n^2 (divide both by n) 

logn vs n

LOGN小於n，比你可以從複雜公式

所以如果複雜度爲O（nlogn + N^2），當n是非常大的，nlogn的值刪除與n^2相比並不重要，這就是爲什麼你刪除它並重寫爲O（n^2）

2017-04-05 20:22:28 Daniel

回答