알고리즘 차수 표기법에서 theta(0)이라는 건.없는 건가요?
글쓴이: gnujina / 작성시간: 월, 2013/10/28 - 10:03오후
어떤 루프에서 전혀 실행되지.않는 단위연산이 있는 경우에서 말입니다.
예컨대 완전히 정렬된 배열을 교환정렬 할 때, 교환연산은 전혀 일어나지 않는데요
이 경우 시간복잡도는 theta(0)이 맞나요?
이런건 사실 들어본적이없지만 theta(1)이라고 하자니 정의에 맞지않네요.
세타에 속하려면 오메가에도 속해야하는데
그럼 0 >= c 를 만족하는 양의실수 c가 있어야 하는데 그럴 수 없죠.
이럴때 Theta(0) 쓰면 맞는건지 궁금합니다
Forums:
정렬되었는지 아려면 적어도 비교연산을 해야하니 여전히
정렬되었는지 아려면 적어도 비교연산을 해야하니 여전히 n*(n-1)/2 = theta(n^2) 입니다.
입력에 상관없이 theta(0)인 코드는 항상 하는일이 없는 셈이니 시간복잡도를 따지는게 무의미한 것 같습니다.
댓글 달기