배열 삽입의 시간 복잡도가 O (n)이고 O (n + 1)이 아닌 이유는 무엇입니까?

Question

방금 ​​데이터 구조를 배우기 시작했는데 배열 삽입을 수행하는 동안 배열 삽입 O (n)의 시간 복잡도가 O (n + 1)이 아닌 이유가 궁금 했습니까?

가장 좋은 경우 삽입이 마지막 위치에있는 경우 시간 복잡도는 O (1)입니다. 여기에 요소가 없으므로 요소를 삽입하려면 1을 고려하고 있다고 가정합니다. 최악의 경우, n 개의 요소를 이동 한 다음 새 요소를 삽입해야한다고 가정하면 시간 복잡도는 O (n + 1)일까요? 요소를 이동하려면 n, 삽입하려면 1을 입력하십시오.

도움을 주신 데 대해 감사드립니다. 감사합니다.

Answer 1

O (n) 인 모든 함수 또한 O (n + 1)이고 그 반대의 경우도 마찬가지입니다. 낮은 순서의 용어는 본질적으로 무시되므로 +1은 아무 의미있는 의미를 부여하지 않습니다.