파이썬 정렬 알고리즘 big-O 시간 복잡도 계산하기

big-O Caculator

v0.0.9.8.3

big-O-calculator

PNGWave

1. 소개

C++ 버전에서 아이디어를 얻어 파이썬으로 모듈화 시키고 pypi에 업로드해보았다.

시간 복잡도를 계산해보는 식은 일반적으로

$T = C * f(n)$, where T = 입력 크기 n의 예측 런타임 , C = 계수 (coeffiecient).

10, 100, 1000, 10,000, 100,000, 총 5번, 5개의 크기만큼 테스트를 돌린다.

 

자세한 사항은 다음 사이트 참고:

github.com/ismaelJimenez/cpp.leastsq

 

2. 설치

pip install big-O-calculator

※ 배열을 파라미터로 받고, 그 배열을 처리하는 함수에서만 작동함 (ex 정렬 알고리즘)

정확히 나오진 않는다, 여러 번 실행해보고 자주 나오는 것으로 판단

 bubble Sort, Selection Sort, Insertion Sort처럼 느린 정렬 알고리즘은 인내심이 필요하다.

 

3. 사용법

정렬이 제대로 되지 않으면 경고가 뜨고 테스트 진행 불가

우선 함수 사용은 다음과 같다.

# array [str]: "random", "sorted", "reversed", "partial", "Ksorted", "string", "almost_equal", "equal", "hole".
test(functionName, array="random", limit=True, prtResult=True)

# ["random", "sorted", "reversed", "partial", "Ksorted", "almost_equal"] 테스트를 돌린 후
# Best, Average, Worst 케이스를 출력한다.
test_all(functionName)

# 단순히 정렬 epoch번 평균 시간 표시
# array = 배열 사용도 가능
runtime(functionName, array="random", size, epoch=1)

# 두 정렬 알고리즘 비교
# array [str]|[List]: "random", "sorted", "partial", "reversed", "Ksorted", 
#        "hole", "equal", "almost_equal", "all" 아니면 직접 배열 pass

compare(bubbleSort, insertSort, "random", 5000)

 

def test(**args):
    functionName [Callable]: a function to call.
    array [str]: "random", "sorted", "reversed", "partial", "Ksorted", "string", "almost_equal", "equal", "hole".
    limit [bool] = True: To break before it takes "forever" to sort an array. (ex. selectionSort)
    prtResult [bool] = True: Whether to print result by itself

def test_all(**args):
    functionName [Callable]: a function to call.

def runtime(**args):
    functionName [Callable]: a function to call.
    array: "random", "sorted", "partial", "reversed", "Ksorted" ,
        "hole", "equal", "almost_equal" or your custom array.
    size [int]: How big test array should be.
    epoch [int]: How many tests to run and calculte average.
    prtResult (bool): Whether to print the result by itself. (default = True)

def compare(**args):
    function1 [Callable]: a function to compare.
    function2 [Callable]: a function to compare.
    array [str]|[List]: "random", "sorted", "partial", "reversed", "Ksorted", 
        "hole", "equal", "almost_equal", "all" or your custom array.
    size [int]: How big test array should be.

 

테스트 배열 예제 (n = 10)

# Test array size 10 example

random = [0, -9, -4, -7, 4, -8, -1, 6, 3, 7]
string = ['9eogsyvcqy', 'frce5gzt1z', 'xx3qqk3x6r', 'ucn2pggk53', 'b1g5ecshqi', 'ok9doelz42', 'ano12ijqvl', 'pwi12fr25i', 'u2by6uwt4c', 'nmj5z5n4sz']
reversed = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
sorted = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
partial = [-8, 0, 2, 3, 4, -1, 6, 0, -4, -7]
Ksorted = [-1, -2, -3, -4, -5, 0, 1, 2, 4, 3]  # K = 4 (10.bit_length()
almost_equal = [10, 11, 9, 11, 10, 10, 11, 10, 9, 10]
equal = [-10, -10, -10, -10, -10, -10, -10, -10, -10, -10]
hole = [5, 5, 5, 5, 5, 5, -9999, 5, 5, 5]

 

test(func, array) - 예제

1. Bubble Sort 시간 복잡도

from bigO import BigO

def bubbleSort(array):  # in-place | stable
    """
    Best : O(n) | O(1) Space
    Average : O(n^2) | O(1) Space
    Worst : O(n^2) | O(1) Space
    """
    isSorted = False
    i = 0
    while not isSorted:
        isSorted = True
        for j in range(len(array) - 1 - i):
            if array[j] > array[j + 1]:
                array[j], array[j + 1] = array[j + 1], array[j]
                isSorted = False
                
        i += 1

    return array

lib = BigO()
complexity = lib.test(bubbleSort, "random")
complexity  = lib.test(bubbleSort, "sorted")
complexity = lib.test(bubbleSort, "reversed")
complexity = lib.test(bubbleSort, "partial")
complexity = lib.test(bubbleSort, "Ksorted")

'''
Running bubbleSort(random array)...
Completed bubbleSort(random array): O(n^2)

Running bubbleSort(sorted array)...
Completed bubbleSort(sorted array): O(n)

Running bubbleSort(reversed array)...
Completed bubbleSort(reversed array): O(n^2)

Running bubbleSort(partial array)...
Completed bubbleSort(partial array): O(n^2)

Running bubbleSort(Ksorted array)...
Completed bubbleSort(ksorted array): O(n)
'''

 

2. Selection Sort (선택 정렬) 시간 복잡도

100,000 크기까지 정렬하는 게 아니고, 10,000 크기 정렬에서 이미 limit이 걸려 일찍 끝난다.

from bigO import BigO

def selectionSort(array):  # in-place, unstable
    '''
    Best : O(n^2) Time | O(1) Space
    Average : O(n^2) Time | O(1) Space
    Worst : O(n^2) Time | O(1) Space
    '''
    for currentIdx in range(len(array) - 1):
        smallestIdx = currentIdx
        for i in range(currentIdx + 1, len(array)):
            if array[smallestIdx] > array[i]:
                smallestIdx = i
        array[currentIdx], array[smallestIdx] = array[smallestIdx], array[currentIdx]

    return array


tester = BigO()
complexity = tester.test(selectionSort, "random")
complexity = tester.test(selectionSort, "sorted")
complexity = tester.test(selectionSort, "reversed")
complexity = tester.test(selectionSort, "partial")
complexity = tester.test(selectionSort, "Ksorted")

''' Result
Running selectionSort(random array)...
Completed selectionSort(random array): O(n^2)

Running selectionSort(reversed array)...
Completed selectionSort(reversed array): O(n^2)

Running selectionSort(sorted array)...
Completed selectionSort(sorted array): O(n^2)

Running selectionSort(partial array)...
Completed selectionSort(partial array): O(n^2)

Running selectionSort(Ksorted array)...
Completed selectionSort(ksorted array): O(n^2)
'''

 

3. Couting Sort (카운트 정렬) 시간 복잡도

from bigO import BigO


def countSort(arr):  # stable
    # Time Complexity : O(n) | Space Complexity : O(n)
    minValue = min(arr)
    maxValue = max(arr) - minValue

    buckets = [0 for _ in range(maxValue + 1)]

    for i in arr:
        buckets[i - minValue] += 1

    index = 0
    for i in range(len(buckets)):
        while buckets[i] > 0:
            arr[index] = i + minValue
            index += 1
            buckets[i] -= 1

    return arr


tester = BigO()

complexity = tester.test(countSort, "random")  # O(n)
complexity = tester.test(countSort, "sorted")  # O(n)
complexity = tester.test(countSort, "reversed")  # O(n)
complexity = tester.test(countSort, "partial")  # O(n)
complexity = tester.test(countSort, "Ksorted")  # O(n)

모든 케이스 O(n)

 

test_all(func) 예제

모든 케이스를 한 번에 돌린 후, 최상, 평균, 최악 케이스를 print 한다.

dictionary를 return 한다.

from bigO import BigO

lib = BigO()

result = lib.test_all(bubbleSort)
result = lib.test_all(insertSort)
result = lib.test_all(selectionSort)

print(result)  # Dictionary


''' Result

Running bubbleSort(tests)
Best : O(n) Time
Average : O(n^2) Time
Worst : O(n^2) Time

Running insertSort(tests)
Best : O(n) Time
Average : O(n^2) Time
Worst : O(n^2) Time

Running selectionSort(tests)
Best : O(n^2) Time
Average : O(n^2) Time
Worst : O(n^2) Time

{'random': 'O(n^2)', 'sorted': 'O(n^2)', 'reversed': 'O(n^2)', 'partial': 'O(n^2)', 'Ksorted': 'O(n^2)'}
'''

 

runtime() 예제

원하는 배열과 크기로 정렬하는데 걸린 시간을 표시한다.

(timeit.default_timer())

from bigO import BigO
from bigO import algorithm

lib = BigO()

timeTook, result = lib.runtime(algorithm.bubbleSort, "random", 5000)

myArr = [0, 0, 0, 0, 0, 0, 0, -1]
timeTook, result = lib.runtime(algorithm.bubbleSort, myArr)

''' Result
Running bubbleSort(len 5000 random array)
Took 2.61346s to sort bubbleSort(random)

Running bubbleSort(len 8 custom array)
Took 0.00001s to sort bubbleSort(custom)
'''

 

compare() 예제

주어진 배열에 따라 두 정렬 알고리즘을 비교한다.

from bigO import BigO
from bigO import algorithm

lib = BigO()

result = lib.compare(algorithm.bubbleSort, algorithm.insertSort, "reversed", 5000)
result = lib.compare(algorithm.insertSort, algorithm.insertSortOptimized, "reversed", 5000)
result = lib.compare(algorithm.quickSort, algorithm.quickSortHoare, "reversed", 50000)
result = lib.compare(algorithm.timSort, algorithm.introSort, "reversed", 50000)
result = lib.compare(sorted, algorithm.introSort, "reversed", 50000)

result = lib.compare(algorithm.bubbleSort, algorithm.insertSort, "all", 5000)

print(result)

'''Result
bubbleSort is 3.6% faster than insertSort on reversed case
Time Difference: 0.04513s

insertSortOptimized is 5959.3% faster than insertSort on reversed case
Time Difference: 1.25974s

quickSortHoare is 153.6% faster than quickSort on reversed case
Time Difference: 0.09869s

introSort is 206.6% faster than timSort on reversed case
Time Difference: 0.12597s

sorted is 12436.9% faster than introSort on reversed case
Time Difference: 0.06862s

Running bubbleSort(tests) vs insertSort(tests)
insertSort is 32.6% faster than bubbleSort on 6 of 8 cases
Time Difference: 0.11975s

{'bubbleSort': 0.4875642249999998, 'insertSort': 0.3678110916666666}
'''

 

@utils.isSorted

from bigO import BigO
from bigO import utils

@utils.isSorted
def bubbleSort(array):  # in-place | stable
    isSorted = False
    counter = 1  # not correct
    while not isSorted:
        isSorted = True
        for i in range(len(array) - 1 - counter):
            if array[i] > array[i + 1]:
                array[i], array[i + 1] = array[i + 1], array[i]
                isSorted = False

        counter += 1

    return array


if __name__ == "__main__":
    bubbleSort(BigO.genRandomArray(100))

''' Result
bubbleSort doesn't sort correctly.
At 99 index: [...99, -76]
'''

 

테스트 케이스 배열 생성기

from bigO import BigO

lib = BigO()

arr = lib.genRandomArray(100)  # 랜덤 배열 (-100 ~ 100)
arr = lib.genRandomBigArray(100)  # 랜덤 큰 수 배열 (100조 크기)
arr = lib.genRandomString(100)  # 랜덤 문자 배열
arr = lib.genSortedArray(100)  # 오름차순 정렬된 배열
arr = lib.genReversedArray(100)  # 내림차순 정렬된 배열
arr = lib.genPartialArray(100)  # 부분 정련된 배열
arr = lib.genKsortedArray(100)  # K정렬된 배열 (K = size.bit_length())
arr = lib.genAlmostEqualArray(100)  # 거의 값이 같은 배열
arr = lib.genEqualArray(100)  # 모두 값이 같은 배열
arr = lib.genHoleArray(100)  # 하나만 값이 작은 배열

 

포함 알고리즘 소스 보기

from bigO import algorithm

import inspect

lines = inspect.getsource(algorithm.insertSortOptimized)
print(lines)  # str


'''Result

def insertSortOptimized(array):
    for i in range(1, len(array)):
        if array[i] >= array[i - 1]:
            continue
        for j in range(i):
            if array[i] < array[j]:
                array[j], array[j + 1 : i + 1] = array[i], array[j:i]
                break

    return array
'''

 

 

포함된 알고리즘을 보려면 아래 사이트를 방문

built-in 알고리즘: github.com/Alfex4936/python-bigO-calculator/blob/master/bigO/algorithm.py

 

Github 링크: github.com/Alfex4936/python-bigO-calculator