+ b = O (n^2)의 시간 복잡도?

Question

"알고리즘 소개"를 읽었으며 저자가 "0보다 큰 경우 임의의 선형 함수 an + b이 O (n^2)에 인 경우 더 놀라운 것은 무엇입니까?"라는 제 3 장에 계속 붙어 있습니다. Can 아무도 그걸 증명할 방법을 설명하지 않습니까?

Answer 1

선형 함수를 정의하여 an + bO(n^2)이다 충분히 큰 n 들어 an + bc = 1 예를 들어, 상수 미만 cn^2이다.

O(n^2)은 상한선이지만 딱딱하지는 않습니다. 더 단단한 경계는 더 엄격한 경계 (이 경우 O(n) 상한)를 증명할 수 있으면 매우 유용하지 않습니다.

Answer 2

직감의 경우, "big O"표기법의 개념은 충분히 큰 입력에서 시작하여 비용 함수가 O (...)보다 빠르게 증가하지 않는다는 것입니다. 그것이 모두 상한 경계 일뿐입니다. 선형 함수는 차 함수, 차 함수, 그들은 모두 빠른 성장 지수 함수 등보다 더 빨리 성장하지 않는

는, 따라서 an + b는 O(n^2)뿐만 아니라 O(n^3), O(2^n), O(n!)이

그러나, 그것은 성장 등이다 로그보다 빠르기 때문에 O(log n)이라고 말할 수는 없습니다.