본고는 시각화 라이브러리와 소프트웨어를 어떻게 사용하여 서로 다른 알고리즘의 운행 시 복잡성을 확정하는지를 소개할 것이다.2D 드로잉 시각화를 위한 matplotlib의 기본 사용법과 최적 의합선을 계산하는 데 사용되는 numpy의 기본 사용법을 소개한 다음 라이브러리를 "추측"또는 이를 실행할 때의 드로잉을 이미 알고 있는 함수(즉 y=x, y=2^n)와 비교하여 실행할 때의 복잡성을 확인하는 방법을 소개합니다.
이 문서의 코드를 다운로드하는 데 관심이 있다면 this repository on my GitHub (chroline/visualizingRuntimes).을 방문하십시오

운행 시 복잡성이란 무엇입니까?

운행시 복잡성은 더욱 구체적으로 말하면 운행시 복잡성 분석으로 알고리즘이 필요한 조작량이 증가할 때 운행 속도를 평가하는 방법이다.우리가 서로 다른 알고리즘의 운행을 시각화하기 전에, 우리는 먼저 몇 가지 기본 예시를 보고 이 개념을 해석할 것이다.
아래의 add 함수를 예로 들자.그것은 두 개의 매개 변수인 a과 b을 받아들여 a과 b에 덧셈을 집행한다.

def add(a, b):
    return a + b

임의의 두 개의 매개 변수(1과 2, 2, 3, 29347과 93648)를 정할 때 조작량은 변하지 않는다.따라서 우리는 이 알고리즘이 일정한 시간, 즉 O(1)으로 운행된다고 말한다.
그러나 현재 아래의 permutations 함수를 고려하고 있다.이것은 주 인자 string을 받아들여 문자열의 모든 배열을 인쇄합니다.

def permutations(string, step = 0):
    if step == len(string):
        print "".join(string)
     for i in range(step, len(string)):
        string_copy = [c for c in string]
        string_copy[step], string_copy[i] =string_copy[i], string_copy[step]
        permutations(string_copy, step + 1)

이 함수는 이전의 add 함수보다 더 긴 시간이 걸린다고 상상할 수 있다.실제로 이 함수는 이른바 곱하기 시간 내에 운행되며 O(n!)으로 표시된다.string의 문자 수가 증가함에 따라 모든 배열을 찾는 데 필요한 조작량이 배로 늘어나기 때문이다.
두 함수의 운행을 직관적으로 비교할 때, 생성된 도형에 선명한 대비가 있음을 알 수 있습니다.add 함수에 대해 평선을 볼 수 있습니다. 함수의 입력은 함수에 필요한 조작량에 영향을 주지 않기 때문입니다.그러나 permutations 함수에 대해 당신은 직선이 급격히 위로 급증하는 것을 관찰할 수 있습니다(직선의 경사율은 무한대에 가깝습니다). 입력 크기가 증가함에 따라 연산량이 배로 증가하기 때문입니다.
우리가 이미 운행시 복잡성 분석의 기초 지식을 소개했기 때문에 우리는 코드를 작성하여 서로 다른 알고리즘의 운행시를 시각화할 수 있다.

초기화

모든 시각화를 실행하기 전에 필요한 라이브러리를 가져와 초기화해야 합니다.

matplotlib은

그래픽을 만들고 표시하는 라이브러리

numpy은 많은 수학 실용 함수

으로 구성된 라이브러리이다

timeit은 하나의 라이브러리로 모든 알고리즘 호출에 필요한 시간을 계산할 것입니다

math은 기본적인 파이썬 수학 라이브러리

입니다.

random은 기본적인 파이썬 랜덤 라이브러리입니다.

import matplotlib.pyplot as plt
import numpy as np
import timeit
import math
import random

plt.rcParams['figure.figsize'] = [10, 6] # set size of plot

데모

다음은 matplotlib과 numpy의 코드 세그먼트를 어떻게 사용하는지 보여 준다.

및 함수

Python sum 함수 계산이 제공하는 Iterable의 모든 원소의 합.이 함수는 운행 시 복잡도가 O(n)인 알고리즘을 실현한다.
이 점을 테스트하기 위해 우리는 linspace 라이브러리의 numpy 방법을 사용하여iterable를 생성하는데 그 중 50개의 값의 간격은 10에서 10000까지 같지 않다.이 그림은 완벽한 직선도는 아니지만 이 점을 설명한다.

ns = np.linspace(10, 10_000, 50, dtype=int)
ts = [timeit.timeit('sum(range({}))'.format(n), number=100)
      for n in ns]

plt.plot(ns, ts, 'or')

우리는 이 점을 한층 더 설명하기 위해 최적합을 한 줄 추가할 수 있다.도표는 영원히 완벽한 직선은 아니지만, 아주 가까울 것이다.

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, ts,'or')
plt.plot(ns, [p(n)for nin ns],'-b')

목록 색인

목록에서 항목(목록 인덱스)을 검색할 때 복잡도는 O(1)으로 목록에 있는 항목의 수량이 알고리즘의 운행 시간에 영향을 주지 않는다는 것을 의미한다.이것은 도표에서 어떻게 표시합니까?

lst = list(range(1_000_000))
ns = np.linspace(0, len(lst), 1000, endpoint=False, dtype=int)
ts = [timeit.timeit('_ = lst[{}]'.format(n),
                    globals=globals(),
                    number=10000)
for nin ns]

plt.plot(ns, ts,'or')

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n)for nin ns],'-b')

계산법

이제 다음 알고리즘으로 생성된 그림을 살펴보겠습니다.

선형 검색

바이너리 검색

삽입 정렬

선형 검색

선형 검색의 운행 복잡도는 O(n)으로 근사직선으로 표시된다.
빨간색 그림은 검색 순서가 없는 목록의 요소를 표시하고, 파란색 그림은 검색 목록에 존재하지 않는 요소를 표시합니다.
빨간색 그림의 최적합선은 보통 파란색 그림의 최적합선보다 작다. 왜냐하면 검색 목록에 존재하지 않는 요소는 전체 목록을 훑어보아야 하기 때문이다.

## searches for an item in a list
def contains(lst, x):
    for y in lst:
        if x == y: return True
    return False

ns = np.linspace(10, 10_000, 100, dtype=int)

# red plots
ts = [timeit.timeit('contains(lst, 0)', 
                    setup='lst=list(range({})); random.shuffle(lst)'.format(n),
                    globals=globals(),
                    number=100)
      for n in ns]
plt.plot(ns, ts, 'or')

# line of best fit for red plots
degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-r')

# blue plots
ts = [timeit.timeit('contains(lst, -1)', 
                    setup='lst=list(range({}))'.format(n),
                    globals=globals(),
                    number=100)
      for n in ns]
plt.plot(ns, ts, 'ob')

# line of best fit for blue plots
degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-b')

바이너리 검색

바이너리 검색의 운행 복잡도는 O(log n)이다.

# searches for an item in a list using linear search
def contains(lst, x):
    lo = 0
    hi = len(lst)-1
    while lo <= hi:
        mid = (lo + hi) // 2
        if x < lst[mid]:
            hi = mid - 1
        elif x > lst[mid]:
            lo = mid + 1
        else:
            return True
    else:
        return False

ns = np.linspace(10, 10_000, 100, dtype=int)
ts = [timeit.timeit('contains(lst, 0)', 
                    setup='lst=list(range({}))'.format(n),
                    globals=globals(),
                    number=1000)
      for n in ns]

plt.plot(ns, ts, 'or')

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-b')

위의 그림은 거의 완벽한 시뮬레이션 그림이다.보시다시피, 몇몇 이상 값이 있습니다. 완벽한 시뮬레이션에서 가장 좋은 의합선은 대수 함수와 같습니다.

삽입 정렬

삽입 정렬은 어떤 운행 시 복잡성이 있습니까?우리는 운행할 때의 그림을 사용하고, 이 그림들을 이미 운행할 때의 그림과 비교하여 가장 가까운 일치를 확정할 수 있다.

def insertion_sort(lst):
    for i in range(1, len(lst)):
        for j in range(i, 0, -1):
            if lst[j-1] > lst[j]:
                lst[j-1], lst[j] = lst[j], lst[j-1]
            else:
                break

# 15 values
ns = np.linspace(100, 2000, 15, dtype=int)
ts = [timeit.timeit('insertion_sort(lst)',
                    setup='lst=list(range({})); random.shuffle(lst)'.format(n),
                    globals=globals(),
                    number=1)
         for n in ns]
plt.plot(ns, ts, 'or');

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-r')

현재, 우리는 이 그림을 서로 다른 운행시의 그림과 비교하여, 어느 것이 가장 비슷하고, 정렬을 삽입하는 운행시의 복잡성을 최종적으로 확정할 수 있다.
빨간색 그림은 O(log n), 파란색 그림은 O(n^2), 녹색 그림은 O(2^n)을 나타낸다.

# y = log x
# vertically stretched 1000x
ns = range(1, 100)
ts = [math.log(n, 2) * 1000 for n in ns]
plt.plot(ns, ts, 'or');

# y = x^2
ns = range(1, 100)
ts = [(n*n) for n in ns]
plt.plot(ns, ts, 'ob');


# y = 2^x
# vertically stretched 20x
# horizontally compressed 1x
ns = range(1, 10)
ts = [math.pow(2, n)*20 for n in ns]
plt.plot(ns, ts, 'og');

이 그림들을 바탕으로 삽입 정렬이 O(n^2) 시간 안에 실행된다고 안전하게 가정할 수 있다.

신비 함수 운행 시 분석

우리는 신비 함수가 운행할 때의 가시화로 그것들의 운행 복잡성을 추측할 수 있습니까?

신비함수 #1

def f(l: list, val): # l is a python list with n items
  d = {}
  for i in range(len(l)):
    d[l[i]] = i
  return d[val]

ns = range(5, 2000)
ts = [timeit.timeit('f(lst, {})'.format(n-1),
                    setup='lst=list(range({})); random.shuffle(lst)'.format(n),
                    globals=globals(),
                    number=1)
         for n in ns]
plt.plot(ns, ts, 'or');

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-b')

이 그림을 실행 가능한 시간도와 비교하지 않더라도, 우리는 이 함수가 O(n)이 실행될 때 실행된다고 안전하게 가정할 수 있다.

신비함수 #2

def g(l): # l is a python list of integers of length n
  pairs = [ (i,j) for i in range(len(l)) for j in range(len(l)) if i < j ]
  result = []
  for (i,j) in pairs:
    if l[i] == l[j]:
      result.append((i,j))
  return result

ns = range(5, 200)
ts = [timeit.timeit('g(lst)',
                    setup='lst=list(range({}))'.format(n),
                    globals=globals(),
                    number=1)
         for n in ns]
plt.plot(ns, ts, 'or')

degree = 4
coeffs = np.polyfit(ns, ts, degree)
p = np.poly1d(coeffs)
plt.plot(ns, [p(n) for n in ns], '-b')

이 그림은 삽입 정렬도와 매우 비슷하기 때문에 우리는 이 함수의 운행 복잡도가 O(n^2)이라고 확정할 수 있다.

신비함수 #3

def h(n):
   if n <= 1:
       return n
   else:
       return h(n-1) + h(n-2)

ns = range(5, 30)
ts = [timeit.timeit('h({})'.format(n),
                    globals=globals(),
                    number=1)
         for n in ns]
plt.plot(ns, ts, 'or')

이 함수는 앞의 두 함수보다 더 모호하다.경사가 O(n)의 증가에 따라 증가할 때 그 운행 시간은 반드시 n보다 커야 한다는 것이 분명하다.빨간색 운행 시 O(n^2)과 파란색 운행 시 O(2^n)의 도표를 고려해 봅시다.

# y = n^2
# vertically stretched 20x
ns = range(5, 30)
ts = [n*n*20000 for n in ns]
plt.plot(ns, ts, 'or')

# y = 2^n
# vertically compressed 50x
ns = range(5, 30)
ts = [math.pow(2, n)/50 for n in ns]
plt.plot(ns, ts, 'ob')

신비 함수 #3의 운행 시 그림은 파란색 그림과 비슷하기 때문에 신비 함수 #3의 운행 시 복잡성은 O(2^n)이다.

결론

이러한 시각화 라이브러리를 사용하면 함수와 알고리즘을 이미 실행 중인 그림/그림과 비교할 수 있다(즉, 정렬 실행 중인 그림과 y=n^2을 삽입하여 비교할 수 있다).운행시의 복잡성을 확정하는 것 외에 이런 방법은 서로 다른 알고리즘의 속도를 비교하는 데도 쓸 수 있다.몇 줄의 코드만 있으면 선택한 알고리즘이 빅데이터 집합에서 실행되는 속도를 신속하게 볼 수 있습니다!

리소스

Pyplot tutorial - Matplotlib 3.4.2 documentation

numpy.polyfit - NumPy v1.20 Manual

Python Program to Display Fibonacci Sequence Using Recursion (programiz.com)

How to find all possible permutations of a given string in Python? (tutorialspoint.com)

8 time complexities that every programmer should know | Adrian Mejia Blog