algorithm - 这是次二次时间吗？

Question

在分析了我正在研究的算法之后，这是运行时间

N    Time
1000   0.019123315811157227
10000   0.11949563026428223
100000   1.4074015617370605
1000000   16.07071304321289

该算法简单地返回 2 个二维数组(“a”和“b”)中的公共(public)点

这是已经使用过的代码

def common_points(a,b): 
    start=time.time()
    specialSuperSorting(a) #Insertion Sort - ~1/4 N^2
    specialSuperSorting(b) #Insertion Sort - ~1/4 N^2
    common=[]
    for i in range(len(a)):
        x=a[i]
        #BinarySearch coordinates(x,y)-Returns True if found, false if not
        y=specialBinarySearch(b,x) 
        if(y):
            common.append(x)
    end=time.time()
    print(len(a),' ',end-start)
    return common

我知道我可以使用更快的排序算法......但我只是选择了更简单的方法来节省我的时间，因为这只是一个练习

那么这是次二次时间吗？以及我如何仅根据 N 与 T(N) 的表来决定...而无需算法本身

Answer 1

算法的运行时间将由其最慢的组件支配。插入排序已经是 O(n^2) 或二次排序，因此您的算法至少会这么慢。假设 specialBinarySearch 是 O(log n)，并且您运行它 n 次，这部分算法将是 O(n log n) .

总而言之，您的算法在 O(1/4 n^2 + 1/4 n^2 + n log n) = O(n^2) 中运行。它是二次的。 1/4 不会改变这一点。您可以在数据中看到这种趋势，如果您将其绘制在图表中，它的上升趋势比线性或 n log n 快得多。