2
무한 시간 수행되는 O (1) 연산은 무엇입니까? 할당 작업 또는 if 조건은 O (1) 시간 복잡도로 간주됩니다. 조건이나 과제가있는 경우 무한한 가능성이 있다고 가정 해 보겠습니다. 총 시간 복잡성은 무엇입니까?O (1) 무한 시간
A
답변
3
최악의 경우, 알고리즘이 제한된 크기의 입력에 대해 무한 수의 단계를 실행하면 알고리즘의 런타임은 함수에 의해 위에 묶여 있지 않으므로 큰 오 또는 작은 오 일이 될 수 없습니다. 모든 기능. Omega 또는 일부 Omega의 기능은 여전히 클 수 있습니다.
어떤 함수에 의해 최악의 경우의 동작을 묶을 수없는 알고리즘은 여전히 일부 함수에 의해 위에 묶여있는 최상의 케이스 또는 심지어 평균 케이스를 가질 수 있습니다 (특정 특정 입력 분포의 경우!). .
2
시간 복잡도는 알고리즘에 정의되어 있으며 정의에 따라 종료해야합니다. 프로그램이 무한 단계를 거치고 종료되지 않으면 "시간 복잡성"이 없습니다.
무한 수의 작업을 수행하는 프로그램은 분명히 종료되지 않습니다. 그것의 복잡성은 입력 크기의 측면에서 표현 될 수 없다. –