[Algorithm] Big-O, 시간 복잡도(Time complexity)

✨시간 복잡도(Time complexity)

문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

 

✨빅오 표기법(big-O notation)

인자가 특정한 값이나 무한대로 향할 때 함수의 극한적인 동작을 설명하는 수학적인 표기법
알고리즘의 시간복잡도는 주로 빅-오 표기법으로 나타낸다.

 

 

 

✨ 상수시간

for n in arr:
    print(1)

주어지는 n값과 상관없이 O(1)의 수행시간을 가진다.

 

 

 

✨선형 시간

for n in arr:
    print(arr[n])

주어지는 n값에 따라 O(n)의 수행시간을 가진다.

 

✨2차 시간

for n in arr:
    for x in arr:
        print(n,x)

주어지는 n값에 따라 O(n^2)의 수행시간을 가진다.

 

 

 

🎈참고자료

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

https://www.freecodecamp.org/korean/news/big-o-notation-why-it-matters-and-why-it-doesnt-1674cfa8a23c/

https://velog.io/@welloff_jj/Complexity-and-Big-O-notation