알고리즘 설계 및 분석 분리

Question

알고리즘의 출력 및 결과를 분석하는 사람들이 설계를 알고 있어야합니까?
분석을하면 알고리즘이 실패하고 잘못된 결과를 반환하는 경우를 찾는 것입니다.

Answer 1

두 가지 유형의 테스트가 있습니다. 첫째, 알고리즘 디자인을 구현하는 코드가 특히 디자인에서 지정된 경계 내에서 작동하는지, 특히 가장자리에서 테스트되는지 기술 테스트가 필요합니다.

두 번째 형식은 알고리즘에 의해 생성 된 출력이 설계 의도와 일치하는지 여부를 확인하기위한 기능 테스트입니다. 이를 위해 구현에 대해 반드시 알 필요는 없으며 그렇지 않은 경우 더 객관적으로 수행된다고 말하는 합리적인 논의가 있습니다.

물론 알고리즘이 간단하고 가능한 모든 결과를 알 수 있다면 테스트는 경계 조건을 실행하는 테스트 데이터를 생성하는 것일뿐입니다.

그러나 알고리즘에 따라 그럴 수도 없습니다. 알고리즘이 쉽게 시각화되지 않은 공간에서 데이터를 분석하는 경우 (27 차원 및 1M 데이터 포인트가 있다고 가정) 기능적인 정확성을 위해 사소한 경우 만 테스트 할 수 있습니다. 분석에서 나온 "옳은"대답은 하나도 없지만 그럴듯한 결과가 많으면 더 나 빠지게됩니다. 이 경우 경험이 풍부한 분석가가 결과를 확인하여 의미가 있는지 확인해야합니다. 때로는 코드를 구현하는 사람과 동일한 사람이 있으며 때로는 그렇지 않습니다. 이러한 경우 구현은 결과를 이해하려고 할 때 거의 확실하게 의문을 제기하게되며, 이는 복잡 할 것입니다.

가능한 한 짧은 대답이지만, 항상 알고리즘을 완벽하게 설명 할 필요는 없습니다.

1. 블랙 두 가지가 매우 중요하다
2. Glassbox

:

Answer 2

는 단위 테스트의 두 가지 종류가 있습니다. 블랙 박스 테스트는 기능 문서 (명시된 입력, 전제 조건, 명시된 결과, 명시된 사후 조건, 명시된 오류 사례 및 그러한 오류가 발생한 경우의 행동/결과)만을 토대로 작성해야합니다. Glassbox 테스트는 구현의 모든 가지가 올바르게 작동하는지 확인하고 구현을 조사해야합니다. 이러한 테스트는 일반적으로 각 실행 분기에 대한 몇 가지 예제 입력을 제공합니다.

사람들이 "알고리즘 분석"에 대해 이야기 할 때 일반적으로 특정 구현에 대해 이야기하는 것이 아니라 오히려 의사 코드를 사용하여 대개 목적을 위해 알고리즘의 이론적 분석을 설명합니다 알고리즘의 정확성을 입증하고 최악의 경우 또는 기대되는 경우 실행 시간에 상한선을 표시합니다. 이러한 분석은 일반적으로 의사 코드 (또는 알고리즘의 행동에 대한 공식적인 설명)를 필요로하며 이에 대한 속성을 추론하고 증명합니다.