python - 大 O 表示法中的 Codility 三角问题

Question

我已经解决了 Codility 的三角形问题，但是我是 Big O Notation 的业余爱好者，我想问一下这个解决方案的时间复杂度是 O(N * logN)？

问题：https ://app.codility.com/programmers/lessons/6-sorting/triangle/

解决方案;

def solution(A):
    # if sorted
    # A[Q] + A[R] > A[P]
    # A[P] + A[R] > A[Q]
    # only needed to check
    # A[P] + A[Q] > A[R]
    A.sort()

    if (len(A) < 3):
        return 0
    
    for i in range(len(A)-2):
        if (A[i] > A[i+2] - A[i+1]):
            return 1
    return 0

标签： pythonpython-3.xbig-o

Answer 1

如for您所料，循环在这里是良性的，并且具有 O(N) 的时间复杂度。

但是，该A.sort()调用具有 O(nlog(N)) 时间复杂度。有关更多详细信息，请参阅Timsort 的 Wikipedia 条目。