Big-O 缩放 - 验证和表示（案例：列表的唯一性）

Question

我有三种不同的方法来检查列表条目的唯一性，理论上 O(N)、O(N log N) 和 O(N**2) 的缩放比例不同，而 N 是长度的名单。

我明白为什么这些方法应该像 O(N)、O(N log N) 和 O(N**2) 那样扩展，但我无法用数字证明它。

这个想法只是运行每个方法多次使用随机列表条目和不同的长度。然后绘制时间与列表长度（即 N）。我预计每个 method/N 的最坏情况应该像理论预测那样扩展，但事实并非如此。

代码：

import time
import random
import matplotlib.pyplot as plt


#O(N**2) - each loop is O(N)
def is_unique1(alist):
    for i in range(len(alist)):
        for j in range(i+1,len(alist)):
            if alist[i] == alist[j]:
                return False
    return True

#O(N log N) - as sort() is O(N log N)
def is_unique2(alist):
    copy = list(alist)
    copy.sort()
    for i in range(len(alist)-1):
        if copy[i] == copy[i+1]:
            return False
    return True    

#O(N) - as set is O(N)
def is_unique3(alist):
    aset = set(alist)
    return len(aset) == len(alist)


times = []
lengths = []
scale = 1.5

for i in range(1,10):
    print('range:',10**i,'to',10**(i+1),'values calc:',int(10**(i/scale)))

for j in range(1,10):
    for i in range(1,int(10**(j/scale))):
        random.seed(42)
        a = str(random.randint(10**j,10**(j+1)))
        start = time.time()
        is_unique3(a)
        end = time.time()
        times.append(end-start)
        lengths.append(len(a))


print(min(times),max(times))

plt.scatter(lengths,times,s=5)
plt.ylabel('process time (s)')
plt.xlabel('N (length of list)')
plt.title('is_unique3')
plt.grid()
plt.ylim(0.9*min(times),1.1*max(times))
#plt.yscale('log')
plt.show()

结果：

遗憾的是，我根本看不出理论预期与数值评估之间的对应关系。

认为可以实现这一目标只是幻想吗？我这样做的方式错了吗？我是否必须检查每个可能的列表条目以获得正确的缩放比例？

我很困惑，希望得到任何提示...

＃＃＃＃＃＃编辑

感谢评论！我改变了收集每个进程时间的方式，并决定对每个列表长度（现在）100 运行s 取平均值。我尝试使用每 100 运行秒的最长时间，但结果看起来仍然是随机的。改编后的代码片段：

import time
import random
import numpy as np
import matplotlib.pyplot as plt


#O(N**2) - each loop is O(N)
def is_unique1(alist):
    for i in range(len(alist)):
        for j in range(i+1,len(alist)):
            if alist[i] == alist[j]:
                return False
    return True

#O(N log N) - as sort() is O(N log N)
def is_unique2(alist):
    copy = list(alist)
    copy.sort()
    for i in range(len(alist)-1):
        if copy[i] == copy[i+1]:
            return False
    return True    

#O(N) - as set is O(N)
def is_unique3(alist):
    aset = set(alist)
    return len(aset) == len(alist)

times = []
lengths = []
times_mean = []
#times_max = []

for j in range(500,10000,1000):
    lengths.append(j)
    for i in range(1,100):
        a = []
        for i in range(1,j):
            a.append(random.randint(0,9))
        start = time.perf_counter()
        is_unique2(a)
        end = time.perf_counter()
        times.append(end-start)
    times_mean.append(np.mean(times))
    #times_max.append(np.max(times))

#print(min(times),max(times))
#print(len(lengths),len(times_mean))

plt.scatter(lengths,times_mean,s=5, label='mean')
#plt.scatter(lengths,times_max,s=5, label='max')
plt.legend(loc='upper left')
plt.ylabel('process time (s)')
plt.xlabel('N (length of list)')
plt.title('is_unique2')
plt.grid()
plt.ylim(0.9*min(times_mean),1.1*max(times_mean))
#plt.yscale('log')
plt.show()

结果：

虽然方法 2 和 3 看起来它们会在某种程度上扩展为 O(N) 或 O(N log N) - 我希望这不是偶然的 - 方法 1 看起来仍然很垃圾，甚至不接近 O(N** 2).事实上，我预计这种方法，作为一个双循环，会差一英里。

我是否还遗漏了一些更一般的东西？

Answer 1

为了改进您的实验，您应该使用相同的数据集来评估所有长度的所有函数。目前，您正在为要测试的每个 n 长度以及要测试的每个函数生成一个新数据集。这将导致不确定的结果。

此外，Big o 只为您的函数提供一个上限，而不是一个确切的数字，它可能会更低（在您的函数中，如果所有元素已经是唯一的）但永远不会超过上限。

Answer 2

您最多只能达到长度 10，增量为 1。在那么短的输入下，您仍然在很大程度上被固定开销所覆盖，并且相邻值之间的区别相当小（n 与 n log n 在任何情况下都不会清楚地显示相邻值）。尝试运行您的输入大小为 100 的测试，然后重复加倍（200、400、800 等），如果您想超越淹没可见结果的固定开销，并且有足够的工作差异以清楚地显示出来即使有轻微的解释器性能抖动（使用 time.time() 而不是更合适的计时机制 like time.perf_counter or the like 会加剧）。

Big-O 缩放 - 验证和表示（案例：列表的唯一性）

Big-O scaling - validation and representation (case: uniqueness of a list)

python

big-o

list