首頁猿問在某些條件下查找歸并排序的時(shí)間復(fù)雜度

在某些條件下查找歸并排序的時(shí)間復(fù)雜度

Java

繁華開滿天機(jī) 2022-10-26 16:54:44

給定一個(gè)更改的合并排序算法，如果數(shù)組已經(jīng)排序，算法將返回?cái)?shù)組，而不是再進(jìn)行 2 次遞歸調(diào)用。假設(shè)我們在一個(gè)數(shù)組上運(yùn)行新算法，其中每個(gè)值恰好出現(xiàn) n/log(n) 次。（為此，該數(shù)組包含 log(n) 不同的值）。該算法的時(shí)間復(fù)雜度是多少？

查看完整描述

1 回答

炎炎設(shè)計(jì)

TA貢獻(xiàn)1808條經(jīng)驗(yàn) 獲得超4個(gè)贊

如果您懷疑數(shù)組具有非常少的不同值，則掃描數(shù)組以提取這些值、對它們進(jìn)行排序和計(jì)數(shù)將比對數(shù)組執(zhí)行完全合并排序花費(fèi)的時(shí)間要少得多：

如果您使用哈希表，選擇值將花費(fèi)O(N)時(shí)間，生成大小為log(N)的樣本數(shù)組。
排序這個(gè)樣本數(shù)組應(yīng)該花費(fèi)O(log(N).log(log(N))，與掃描階段相比可以忽略不計(jì)。
枚舉樣本數(shù)組以生成原始數(shù)組的副本也具有線性時(shí)間復(fù)雜度O(N)。

因此，時(shí)間復(fù)雜度可以降低到O(N)。

但請注意：

使用哈希表可能無法構(gòu)建樣本數(shù)組。相反，如果您構(gòu)建一個(gè)排序列表，則復(fù)雜性會跳回到O(N.log(N))，因?yàn)榫€性查找每個(gè)元素的樣本數(shù)組。
如果原始數(shù)組的元素具有相同的鍵但內(nèi)容不同，則生成元素的副本可能不夠。在這種情況下，您將掃描原始數(shù)組并在示例數(shù)組中查找元素的鍵，以確定將元素存儲在結(jié)果數(shù)組中的位置，如果示例數(shù)組是列表，則再次O(N.log(N))時(shí)間復(fù)雜度, 和O(N.log(log(N)))如果它是一個(gè)數(shù)組并且你使用二進(jìn)制搜索。

總而言之，在特殊情況下可以有效地降低復(fù)雜性，但在一般情況下卻很棘手。

反對回復(fù) 2022-10-26