얼레벌레 얼레벌레

시간 복잡도 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계 공간 복잡도 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계 평균 시간 복잡도 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균 최악 시간 복잡도 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간 빅오 notation 점근 표기법의 하나 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현 (알고리즘의 복잡도를 표현할 때 흔히 쓰임) o(logn): 입력의 크기의 로그에 비례하는 시간 소요 o(n) : 입력의 크기에 비례하는 시간 소요 계수는 그다지 중요하지 않음 선형시간 알고리즘 - o(n) 예 : n개의 무작위로 나열된 수에서 최댓값을 찾기위해 선형탐색 알고리즘을 적용 최댓값 - 끝까지 다 살펴보기 전까지..