맞는 말입니다. 다만 저렇게 잘 쓰지 않습니다.
어떤 함수 g(N)이 O(f(N))이라는 것은 N이 클 때 g(N)/f(N)이 어떤 상수 이하가 된다는 의미입니다.
N이 클 때 NlogN은 N^2에 비해 무시할 수 있을 만큼 작아지기 때문에 , 특별한 이유가 없다면 O(NlogN + N^2)처럼 쓰지 않고 그냥 O(N^2)이라고 표기합니다.
big O 노테이션은 일종의 집합을 가리키는 말이기 때문에 O(NlogN) + O(N^2)라는 표기는 그다지 좋은 표기가 아닙니다만, 정의하자면 정의할 수도 있고 누가 뭐라고 하지는 않습니다.
youmr101 4년 전
안녕하세요 알고리즘 문제 열심히 풀어보고 있는 알고리즘어린이입니다
시간복잡도에 관한 글을 좀 읽어봤는데요 확실히 이해하지 못한것같아 질문드립니다
만약 N과 N개의 정수를 입력받았습니다
문제를 해결하기 위한 알고리즘을 적용하는데 있어 조건이 정렬된 배열이고
알고리즘의 시간복잡도는 O(N^2) 이라 하면
"이 문제 해결을 위한 시간복잡도는 O(NlogN + N^2)이다"
이 말이 맞는말 인가요?
즉 시간복잡도라는 개념이 알고리즘이 아니라 어떤 문제를 해결하기 위해 필요한 시간을 나타낼때도 쓸수있는건가요?
그리고 위와 같은 상황에서는 O(NlogN) + O(N^2), O(NlogN + N^2) 중 어떻게 쓰는게 맞는건가요?
답변해주시는 고수님께 미리 감사드립니다..