在合併排序算法的分析中，'6n'（6n（logn + 1）= 6nlogn + 6n）是什麼？

實現合併所需的操作次數爲：在合併排序算法的分析中，'6n'（6n（logn + 1）= 6nlogn + 6n）是什麼？

:::::: 6n（logn + 1）= 6nlogn + 6n。

logn + 1是合併排序中的級別數。這裏6n是什麼？

2016-09-20 Sumanth Ydt

我不確定「什麼是6n」是什麼意思？如果您詢問算法的複雜性（合併排序），則可以將其簡化爲nlog（n）。您可以忽略問題中的係數，因爲在解決大O複雜性時它們可以忽略不計。在計算nlog（n）+ n時，您也可以忽略n，因爲它將以比nlog（n）慢得多的速率增加。這給你帶來了nlog（n）的複雜性。

來源

2016-09-20 06:10:04 PrestonM

在粗合併排序的情況下：兩個讀取比較兩個元素，一個讀取和一個寫入以將較小元素複製到工作陣列，然後再讀取另一個寫入以將元素複製回原始陣列，每個元素總共有6次內存訪問（除了邊界情況，例如達到運行結束時，在這種情況下，其他運行的剩餘部分只是沒有比較地複製）。更優化的合併排序通過交替合併方向（如果自下而上取決於合併通道）來避免複製後退步驟，或者如果自頂向下取決於遞歸級別，則將6減少到4.如果元素適合寄存器，則在一個比較，該元素將在一個寄存器中，不會被重新讀取，將6減少到3.

來源

2016-09-20 06:55:20 rcgldr

在合併排序算法的分析中，'6n'（6n（logn + 1）= 6nlogn + 6n）是什麼？

回答

相關問題