목록Time Complexity (1)

조금씩 꾸준히 완성을 향해

알고리즘의 시간복잡도(Time Complexity) / Big-O 표기법

Time Complexity 수행시간이란 특정 입력에 대해 수행되는 알고리즘의 기본연산(primitive operation)의 횟수를 말한다. (가상컴퓨터에서 가상언어로 작성된 가상코드를 실행한다고 가정 알고리즘의 수행시간 = 최악의 경우의 입력(worst-case input)에 대한 기본연산의 수행 횟수 입력의 크기 n에 대한 함수 T(n)으로 표기 -> 어떠한 입력에 대해서도 T(n) 시간 이내에 종료됨을 보장 ▶ example #input : n개의 정수가 담긴 배열 A #output : A의 수 중에서 최대값 def func(A, n): max = 0 # 1번(할당) for i in A: if i > max: # n-1번(크기를 확인하는 최악의 경우) max = i # n-1번(할당을 하는 최악의..
DataStructure & Algorithm/이론 정리 2022. 9. 26. 23:11
이전 Prev 1 Next 다음