알고리즘 학습

2장. 알고리즘 분석하기

이 작품은 AI를 사용하여 번역되었습니다. 여러분의 피드백과 의견을 환영합니다: [e-mail]

이 장에서는 학습 내용을 살펴봅니다:

• Big O 표기법을 사용하여 알고리즘의 성능을 분류하는 방법(시간 또는 저장 공간)

• 다음과 같은 여러 성능 클래스가 있습니다:

  • O(1) 또는 상수

  • O(log N) 또는 로그

  • O(N) 또는 선형

  • O(N log N)¹

  • O(^N2) 또는 이차적

• 점근 분석이 알고리즘이 N 크기의 문제 인스턴스를 처리하는 데 필요한 시간(또는 저장 공간)을 N의 관점에서 추정하는 방법.

• 값이 오름차순 정렬된 순서로 표시되는 배열로 작업하는 방법.

• 정렬된 배열에서 값을 찾기 위한 이진 배열 검색 알고리즘입니다.

이 장에서는 이론가와 실무자 모두가 계산 성능과 리소스 사용 측면에서 알고리즘의 성능을 모델링할 때 사용하는 용어와 표기법을 소개합니다. 소프트웨어 프로그램의 런타임 성능을 평가할 때 완벽하게 만족할 수 있으며, 이 경우 애플리케이션을 그대로 계속 사용할 수 있습니다. 하지만 런타임 성능을 개선하고 싶다면 이 책에서는 프로그램의 데이터 구조와 알고리즘에서 시작해야 할 부분을 보여줍니다. 몇 가지 구체적인 질문에 직면하게 될 것입니다:

가장 효율적인 방법으로 특정 문제를 해결하고 있나요?

성능을 크게 개선할 수 있는 다른 알고리즘이 있을 수 있습니다.

가장 효율적인 방식으로 알고리즘을 구현하고 있나요?

제거할 수 있는 숨겨진 성능 비용이 있을 수 있습니다.

더 빠른 컴퓨터를 사야 하나요?

똑같은 프로그램이라도 실행되는 컴퓨터에 따라 런타임 성능이 달라집니다. 이 장에서는 컴퓨터 과학자들이 정기적인 하드웨어개선을 고려한 분석 기법을 개발한 방법을 설명합니다.

먼저 계속 증가하는 문제 인스턴스 크기에서 프로그램의 런타임 성능을 모델링하는 방법을 보여드리겠습니다. 작은 문제 인스턴스 크기에서 알고리즘의 런타임 성능은 문제 인스턴스의 실제 값이나 컴퓨터 타이머의 해상도에 민감할 수 있기 때문에 정확하게 측정하기 어려울 수 있습니다. 프로그램이충분히 큰 문제 인스턴스를 처리하면 경험적 모델을 사용하여 런타임 동작을 분류하는 모델을 개발할 수 있습니다.

경험적 모델을 사용하여 성과 예측하기

이론적 분석이 실제 소프트웨어 시스템에서 어떻게 실용적인지 보여주는 예로 시작하겠습니다. 매일 밤 대규모 데이터 집합을 처리하는 야간 배치 작업의 일부로 애플리케이션을 설계하고 자정에 시작하여 오전 6시 이전에 완료해야 하는 작업을 담당한다고 가정해 보겠습니다. 데이터 집합에는 수백만 개의 값이 포함되어 있으며 향후 5년 동안 그 크기가 두 배로 증가할 것으로 예상됩니다.

작동하는 프로토타입을 만들었지만 각각 100개, 1,000개, 10,000개의 값이 있는 여러 개의 작은 데이터 세트에서만 테스트했습니다.표 2-1은 이러한 데이터 세트에서 프로토타입의 런타임 성능을 보여줍니다.

표 2-1. 프로토타입 런타임 성능