1
我在這裏有一個算法。無法定義此算法的運行時間
Click here to check algorithm image
它做什麼，它遍歷數組，發現3個最大數值，並返回它們的總和。 例如，一個數組[1,2,3,4,5]將返回12（3 + 4 + 5 = 12）。
圖像中的算法說它是O（nlogk）。但那是我無法理解的。
追隨中是我講第一個for循環的圖像透視：
堆的方法 「插入（）」 和 「deleteMin（）」，它們都需要O（LOGN）。因此，在第一個for循環中，它通過添加它們的運行時間（它簡單地爲O（logn））來生成O（2 * logn）。由於循環的第一個for循環遍歷數組中的所有元素，所以第一個for循環的總運行時間爲O（nlogn）。
以下是我對第二個觀點while循環的圖像：
從前面的for循環中，我們如果水平尺寸（）>ķ刪除了一些極小值。所以堆中的值的數目是k。 「sum = sum + h.min（）」採用O（logn），因爲如果我知道正確，在堆中搜索最小值需要O（logn），而「h.deleteMin（）」也需要O（logn），因爲它必須再次搜索並刪除。所以O（2 * logn）是通過添加它們的運行時間，這簡直就是O（logn）。由於我們迭代這個while循環只有k次，因爲有k個元素，所以第二個while循環導致O（k * logn）
所以我們有O（nlogn）從第一個for循環，並且O（k logn）從第二while循環。顯然O（nlogn）大於O（k logn），因爲k是某個常數。因此，該算法最後以O（nlogn）結尾。
但答案表示它是「O（nlogk）」而不是「O（nlogn）」。
你能解釋一下原因嗎？