F(n) = n^2+2n+1 일 경우 O(n^2) 오메가(n^2) 세타(n^2) 이잖아요
제가 지금까지 본 다항식은 모두 빅오와 오메가가 같고 결국 세타도 같은 다항식만 보고 있는데 이게 아닌 경우를 예시로 설명해주시면 감사하겠습니다.
또한 베스트 워스트 에버리지도 있는데 베스트는 항상 T(1) 인가요? 그리고 빅오가 워스트인지 궁금합니다.
마지막으로 베스트는 Tb(n) 워스트는 Tw(n) 에버리지는 Ta(n) 으로 표기하던데 그냥 T(n) 이렇게 해놓는것은 무엇을 적으라는 건가요?
뭔가 크게 착각하고있는것 같은데 저 노테이션들의 관계는 다항식 하나만 가지고 이야기하는게 아니고 니가 풀려고했던 문제에 대해 이야기하는거임
문제에서 Tw(n)=n^2+2n만 주고 Tb(n) Tw(n) Ta(n) T(n)을 구하라고해서요
아니 물론 알고리즘 자체의 복잡도를 나타내는 표현에서는 맞기는한데 이해하기에는 문제로부터 얻어낸다고 이해하는게 도움될듯
베스트는 뭐 계수도 따지겠지 같은 O(1)이라도
네 감사합니다. 위에 말한 문제처럼 다항식을 통해서만 도출하려고한다면 베스트 워스트 에버리지 모두 n^2인가요? T(n) 은 무엇을 말하는지 모르겠네요 ㅠㅠ 독학이라
모든 입력에 대해서 F(n)의 형태면은 베스트 = 워스트 = 에버리지 다 n^2으로 같은거지
근데 대부분의 알고리즘이 입력값에 대해 각자 다른 결과가 나온다 예를들어 바이너리 서치같은경우 최대 log n이 걸리겠지만(O(logn)) 입력값이 좋아서 중간에 찍히면 1번만에 잡힐수도있는거지 이떄문에 저런 표기법들이 나온거고
베스트가 항상 1이 아닌경우를 예로들면 어떤 프로그램인데 항상 n개의 입력을 읽어들여야되는 상황이면 아무리 빠른 알고리즘이라도 n번 읽어야되니까 최소 n은 걸린다고 말할수있지