자료구조 #IT #컴퓨터공학과 #알고리즘 #알고리즘시간복잡도
-
알고리즘의 시간 복잡도 총 정리Computer Science/알고리즘 2020. 8. 16. 21:53
무거운 프로그램일 수록 처리하는 데이터가 많아지고 처리하는 작업이 복잡해질수록 시간은 매우 중요해집니다. 그래서 개발자들은 상황에 따라 특정 알고리즘을 유연하게 사용할 수 있어야 합니다. 특정 알고리즘의 실행시간을 표기하는 용어는 아래와 같습니다. Big O 표기법에서 O 는 "on the order of"의 약자로 "~만큼의 정도로 커지는" 것이라고 해석됩니다. O(n)은 n만큼 커지는 것이므로 n이 늘어날수록 선형적으로 증가하게 됩니다. O(n/2)는 n이 무한대로 커지면 1/2는 결국 의미가 없어지므로 O(n)과 같은 의미로 볼 수 있습니다. Big Ω표기법은 반대로 알고리즘 실행시간의 하한을 나타낸 것입니다. 예를 들어 선형 검색은 n개의 항목이 있을 때 앞에서부터 차례로 하나씩 검색하므로 총 n..