프로그램 실행 시간이 측정 값이 아닌 이유는 무엇입니까?

Question

나는 프로그램이 그것의 복잡성으로 측정된다는 것을 배웠다 - 나는 Big O Notation을 의미한다. 절대 실행 시간으로 측정하지 않는 이유는 무엇입니까? 감사합니다 :)

Answer 1

절대 실행 시간 대신 알고리즘의 복잡성을 사용하면 프로그램의 절대 실행 시간이 사용 된 알고리즘과 입력 크기에 달려 있기 때문에 알고리즘에 대한 이유를 추론 할 수 있습니다. 또한 실행중인 시스템, 다양한 구현 세부 사항 및 현재 시스템 리소스를 사용하는 다른 프로그램에 따라 다릅니다. 동일한 시스템에서 동일한 입력을 사용하여 동일한 애플리케이션을 두 번 실행하더라도 정확히 동일한 시간을 얻지는 못합니다.

결과적으로 프로그램을 실행하면 프로그램의 실행 시간이 입력보다 훨씬 많은 요소에 의존하기 때문에 "이 프로그램은 크기가 n 인 입력으로 실행될 때 20 * n 초가 걸릴 것"과 같은 문장을 작성할 수 없습니다 크기. 그러나 "이 프로그램의 실행 시간은 O (n)"과 같은 문구를 작성할 수 있으므로 훨씬 유용합니다.

Answer 2

절대 실행 시간은 알고리즘이 다른 입력 집합과 함께 커지는 방식을 나타내는 지표가 아닙니다. 모든 실제 데이터 세트에 대해 O (n * log (n)) 알고리즘이 O (n^2) 알고리즘보다 훨씬 느릴 수 있습니다.

Answer 3

실행 시간은 복잡성을 측정하지 않으며 성능 만 측정하거나 작업 수행에 필요한 시간 만 측정합니다. MP3 플레이어는 노래를 재생하는 데 필요한 시간 동안 실행됩니다. 이 경우 경과 된 CPU 시간이 더 유용 할 수 있습니다.

복잡도의 한 가지 척도는 더 큰 입력으로 확장되는 방법입니다. 이는 필수 하드웨어를 계획하는 데 유용합니다. 모든 것이 평등하고, 상대적으로 선형 적으로 비례하는 것이 비늘이 잘리는 것보다 바람직합니다. 사물은 거의 동일하지 않습니다.

다른 복잡도는 코드가 얼마나 간단한지를 나타내는 척도입니다. 상대적으로 선형 인 성능 복잡성을 가진 프로그램의 경우 코드 복잡성이 보통 더 높습니다. 복잡한 코드는 값 비싼 유지 관리가 필요할 수 있으며 변경하면 오류가 발생할 가능성이 큽니다.

모든 세 가지 (또는 네 가지) 측정 값이 유용하며 그 중 아무 것도 그다지 유용하지 않습니다. 3 가지가 함께 사용하면 매우 유용 할 수 있습니다.

Answer 4

질문에 좀 더 많은 문맥을 사용할 수 있습니다.

실제 프로그램을 프로그래밍 할 때 우리는 프로그램의 실행 시간을 측정 할 것입니다. 1. 프로그램이 실행되는 하드웨어는 무엇입니까? 다른 하드웨어에서 실행되는 두 개의 프로그램을 비교하는 것은 의미있는 비교를 제공하지 않습니다. 2. 실행중인 다른 소프트웨어는 무엇입니까? 달리 실행하면 CPU주기 (또는 프로그램에서 실행중인 다른 리소스)를 훔칩니다. 3. 입력 내용은 무엇입니까? 이미 말했듯이, 작은 세트의 경우 솔루션은 매우 빨라 보이지만 확장 성은 문제가되지 않습니다. 또한 일부 입력은 다른 입력보다 쉽습니다. 만약 사람으로, 당신은 나에게 사전을 건네고, 나에게 정렬을 부탁하면, 나는 그것을 바로 돌려주고 끝이라고 말할 것이다. 나에게 무작위 순서로 50 장의 카드 (사전보다 훨씬 작음) 세트를 주면 훨씬 더 오래 걸릴 것입니다. 4. 시작 조건은 무엇입니까? 프로그램이 처음으로 실행되는 경우, 하드 디스크에서 회전시켜 현대 시스템에서 가장 큰 시간을 차지할 가능성이 있습니다. 두 개의 구현을 작은 입력과 비교하는 것은 이것에 의해 가려진 차이점을 가질 가능성이 높습니다.

Big O 표기법은 이러한 많은 문제를 다룹니다. 1. 모든 작업이 1 작업 속도 O (1)로 표준화되므로 하드웨어는 중요하지 않습니다. 2. 빅 오 (Big O)는 알고리즘과 관련하여 다른 알고리즘이 없다고 말합니다. 3. 빅 오 (Big O)는 입력이 얼마나 오래 걸리는지가 아니라 실행 시간이 어떻게 바뀌는 지 이야기합니다. 평균 또는 쉬운 입력에서 수행하는 방식이 아니라 알고리즘이 수행하는 최악의 상황을 알려줍니다. 4. 다시 Big O는 알고리즘을 처리하지만 실제 시스템에서 실행되는 프로그램은 처리하지 않습니다.