时间复杂度 - O(n^2) 到 O(n log n) 搜索

Question

我有一个 n 项目的无序列表，我正试图在该列表中找到最常见的项目。我写了下面的代码：

def findFrequant(L):
     count = int()
     half = len(L)//2
     for i in L:
          for j in L:
               if i == j:
                    count += 1
                    if count > half:
                         msg = "The majority vote is {0}".format(i)
                         return msg
               else:
                    continue
          count = 0
     return "mixed list!"

显然这个包含两个循环的过程是 O(n^2)，我正试图在 O(n log n) 时间内完成相同的任务。我不是在寻找修复程序或有人为我编写代码，我只是在寻找方向。

Answer 1

您可以使用合并排序，其最坏情况时间复杂度为 O(n log(n)) 和二分查找，其最坏情况时间复杂度为 O(log(n))。

有些排序算法具有更快的最佳情况，例如冒泡排序的最佳情况为 O(n)，但合并排序在最坏情况下的执行时间为 O(n log(n))，而冒泡排序的最坏情况为 O(n^2)。

像我们计算机科学家一样悲观，我们通常根据最坏的情况进行分析。因此，合并排序和二进制搜索的组合可能最适合您的情况。

请注意，在某些情况下，基数排序可能比合并排序执行得更快，但这实际上取决于您的数据。

Answer 2

我不认识这里的语言，所以我将其视为伪代码。

这取决于一个散列表，其键为L元素类型，值类型为int。对哈希表中的每条记录进行计数，然后将哈希表作为键值对的正常集合进行迭代，应用正常的最大列表算法。

O(n)比线性稍差。我们记得，好的哈希的开销不是线性的，但可以近似为线性的。使用线性 space。

def findFrequant(L):
     hash = [,]
     vc = 0
     vv = null
     for i in L
         if hash.contains(i)
             hash[i] = hash[i] + 1
         else
             hash[i] = 1
     for (k,v) in hash
         if v > vc
             vv = k
             vc = v
         else if v == vc
             vv = null
     if (vv == null)
         return "mixed list!"
     else
         return "The majority vote is {0}".format(v)

时间复杂度 - O(n^2) 到 O(n log n) 搜索

Time complexity - O(n^2) to O(n log n) searching

algorithm

big-o

search

time-complexity