[Python] 알고리즘의 시간 복잡도

알고리즘

평소 어느 목적지로 이동을 할 때 우리는 자연스럽게 최단거리, 최소시간을 생각하며 움직인다.

10이라는 시간으로 갈 수 있는 목적지인데 굳이 100의 시간을 들여 다른 길로 가려하지 않는다.

 

프로그래밍에서는 목적지로 가는 수많은 과정(루트)을 알고리즘이라 말할 수 있으며,

알고리즘의 실행 시간(처리 시간)을 최소화 하기 위한 노력을

알고리즘의 시간복잡도를 개선한다라고 표현할 수 있다.

 

즉, 최소한의 시간과 공간을 이용해 문제를 해결하는 과정이 좋은 알고리즘이라고 할 수 있다.

 

시간 복잡도와 점근 표기법(Big - O)

시간 복잡도는 간단히 말해 알고리즘이 동작하는데 시간이 얼마나 걸리는 지

수치화하여 표현한 것이다.

 

Big - O 표기법은 알고리즘의 시간복잡도를 단순화 할 때 사용하는 표기법으로,

최악의 시간복잡도에도 O(_) 만큼의 성능은 보장함을 의미한다.

 

표현할 복잡도의 최대차수의 항을 제외한 나머지 모든 항 및 최대 차수 항의 계수를 제거하여 표현한다.

 

**ex

2N^2+N+1 의 복잡도를 가지는 알고리즘을 Big - O 표기법으로 나타내면,

O(N^2)이 된다.

 

시간 복잡도의 대소 관계를 Big - O 표기법으로 표현해 보면 다음과 같다.

 

O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!)

<--- 빠름  ------------------------------------------------------ 느림 --->

 

https://www.bigocheatsheet.com/

"""
약수 구하기
"""

n = int(input())
lst = []               # 1

def my_func(n):
    for i in range(1, n + 1):   # N
        if n % i == 0:          # N
            lst.append(i)       # 1

    return print(lst)           # 1

my_func(n)

# input : 10
# [1, 2, 5, 10]
# O(N)