빅오 표기법 - 파이썬-파이썬 튜토리얼-php.cn

집

백엔드 개발

파이썬 튜토리얼

빅오 표기법 - 파이썬

Barbara Streisand

Nov 18, 2024 am 08:43 AM

1. 정의

알고리즘의 실행 시간이나 공간 사용량의 상한을 설명하는 수학적 표기법입니다. O(f(n))으로 표시하는데, 여기서 f(n)은 입력 n의 크기에 따른 시간이나 공간을 나타내는 함수이다. .

Notación Big O - Python
자세한 내용은 http://bigocheatsheet.com

을 참조하세요.

2. 목적

알고리즘 비교: 다양한 알고리즘을 비교하고 주어진 문제에 가장 효율적인 알고리즘을 선택할 수 있습니다.
확장성: 데이터 양이 증가할 때 알고리즘이 어떻게 작동할지 예측하는 데 도움이 됩니다.

3. 복잡성 분석

최악의 경우: 알고리즘이 더 오래 걸리거나 더 많은 리소스를 사용하는 시나리오를 말합니다. 빅오는 주로 이런 경우를 지칭합니다.
최고 사례 및 평균 사례: 중요하지만 Big O 표기법에서는 덜 자주 사용됩니다.

4. 우주 대 우주 시간

시간적 복잡도: 알고리즘이 실행되는 데 걸리는 시간을 말합니다.
공간 복잡도: 추가로 사용하는 메모리의 양을 나타냅니다. O(1)(상수 공간) 또는 O(n)(선형 공간)

예:

import timeit
import matplotlib.pyplot as plt
import cProfile

# O(1)


def constant_time_operation():
    return 42

# O(log n)


def logarithmic_time_operation(n):
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

# O(n)


def linear_time_operation(n):
    total = 0
    for i in range(n):
        total += i
    return total

# O(n log n)


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

# O(n^2)


def quadratic_time_operation(n):
    total = 0
    for i in range(n):
        for j in range(n):
            total += i + j
    return total

# O(2^n)


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

# O(n!)


def factorial_time_operation(n):
    if n == 0:
        return 1
    else:
        return n * factorial_time_operation(n - 1)

# Function to measure execution time using timeit

def measure_time(func, *args):
    execution_time = timeit.timeit(lambda: func(*args), number=1000)
    return execution_time


def plot_results(results):
    functions, times = zip(*results)

    colors = ['skyblue', 'orange', 'green', 'red', 'purple', 'brown', 'pink']
    plt.figure(figsize=(14, 8))
    plt.bar(functions, times, color=colors)

    for i, v in enumerate(times):
        plt.text(i, v + 0.5, f"{v:.6f}", ha='center',
                 va='bottom', rotation=0, color='black')

    plt.xlabel('Function Complexity')
    plt.ylabel('Average Time (s)')
    plt.title('Execution Time of Different Algorithm Complexities')
    plt.grid(axis='y', linestyle='--', linewidth=0.5, color='gray', alpha=0.5)

    plt.tight_layout()
    plt.show()


def main():
    results = []
    results.append(("O(1)", measure_time(constant_time_operation)))
    results.append(("O(log n)", measure_time(logarithmic_time_operation, 10)))
    results.append(("O(n)", measure_time(linear_time_operation, 10)))
    results.append(("O(n log n)", measure_time(
        linear_logarithmic_time_operation, 10)))
    results.append(("O(n^2)", measure_time(quadratic_time_operation, 7)))
    results.append(("O(2^n)", measure_time(exponential_time_operation, 7)))
    results.append(("O(n!)", measure_time(factorial_time_operation, 112)))

    plot_results(results)


if __name__ == '__main__':
    cProfile.run("main()", sort="totime", filename="output_profile.prof")

로그인 후 복사

Notación Big O - Python