최선의 시간복잡도를 얘기하면

[공도르(1.244)]

예를 들어 서치 알고리즘에서 최선의 경우 단 한번에 찾을 수 있다면 최선의 시간복잡도를 물어봤으니

점근적 표기법으로 꼭 세타표기를 써야하나요? 아니면 O(1)을 써야하나요?

[매애액(223.38)]

시간복잡도 보통 빅오표현만 쓰지않음? 나머지는 학부때 배우고 한번도안써서 잊어버림

[공도르(1.244)]

네 보통 알고리즘 시간복잡도는 빅오만 쓴다고 알고 있는데 문제에서 최선최악평균을 써놓고 이것에 대한 점근적 표기법을 쓰라고 해서.. 다 빅오로 써야하는지 아니면 저렇게 나눠논거는 빅오 빅오메가 빅세타를 쓰라고 하는지 모르겠네요 ㅠㅠ

[매애액(223.38)]

문제가 뭔지 모르겠지만 퀵소트로 예를들자면 인풋에따라 최악의경우에는 n2이 걸리고 일반적으로는 nlogn에 비례한다 이런거아님? 빅오로

[공도르(1.244)]

http://gall.dcinside.com/board/view/?id=programming&no=781102&page=1&search_pos=&s_type=search_all&s_keyword=시간복잡도
한번 확인해주실수있나요? 제가 올렸던 문제입니다

[매애액(223.38)]

tb tw같은게 뭔지몰라서 못말해주겠음. 빅오로는 n2 n n2

[츄럴(rhdnfka94)]

최선 최악 평균이랑 표기법은 다른 거 같음

[공도르(1.244)]

Tb가 최선 Tw가 최악 Ta가 평균이라 이걸 매애액님 처럼 빅오로만 써야할지 아니면 최선최악평균이니 빅오 빅오메가 빅세타를 써야할지 모르겠네용

[츄럴(rhdnfka94)]

오메가 세타 오 는 그냥 하한 중간 상한을 의미하는 거고 ㅇㅇ

[공도르(1.244)]

네 문제에서도 최선최악평균을 점근적 표기법으로 쓰라고 즉 빅오같은 표기법을 쓰라고했는데 전부 빅오로 갈지.. 아니면 위에 말했듯이 최선은 오메가 최악은 오 평균은 세타로 가야할지 모르겠네염

[공도르(1.244)]

그러면 그냥 빅오로만 쓰면 될까요? 그렇게 되면 (a),(c)는 모두 O(n^2) 이고 (b)만 O(n) 이네요?

[츄럴(rhdnfka94)]

표기법 3가지가 의미가 다른데 적절히 해야되지 않을까용

[매애액(223.38)]

아니면 입력에따라 a는 0이될수도있고 b는 입력이아무리작아도 1만큼 c는 3만큼 필요하다는걸 쓰라는건가.

[공도르(1.244)]

문제에서 T(n)은 고정이라 입력값은 변동이 없는거같아요

[공도르(1.244)]

그리고 (a) 같은 경우 최악의 경우만 줬는데 이걸로 T(n)은 어떻게 구하라는건지 -_-;;; 그냥 O(n^2)만 다 쓰라고 써논건지 각각 최선은 오메가 최악은 오 평균은 세타 T(n)은 ..? 의도를 모르겠네요 ㅠㅠ