학문/계산이론 (1) 썸네일형 리스트형 계산 복잡도 이론(Time Complexity Theory) 오늘은 계산 복잡도 이론에 대해 잠깐 알아보겠다. 어떤 문제를 푸는 데에는 어떠한 알고리즘이 필요하다. 어떤 문제는 풀기 쉽고, 어떤 문제들은 풀기 어렵다. 예를 들어서. 어떤 숫자의 리스트를 정렬하는 것은 쉬운 문제이다. 이미 알려진 알고리즘도 굉장히 많다. 선택 정렬, 삽입 정렬, 거품 정렬 등등.... 그리고 시간 복잡도도 정렬에 따라 O(n^2) 아니면 O(nlogn)임을 알 수 있다. 반면 가장 효율적으로 대학 수업들을 서로 강의실과 시간이 겹치지 않게 모두 정렬하는 것은 어려운 문제이다. 고려해야 할 시간과 강의실도 있고, 무엇보다 그 수업들이 겹치지 않도록 해야 한다. 하지만, 알고리즘을 생각해 낸다고 해서 그 알고리즘이 가장 효율적인 것은 아니다. 예를 들어, 어떤 두 자연수가 서로소인지를.. 이전 1 다음
