시간 복잡도가 뭐에여

ㅇㅅㅇ
0(n log n) 이런게 뭘 의미하는지 궁금합니다

1 Like

O(n log n)은 n=1000일 때,
프로그램이 아무리 그지같이 돌아가도 1000*log1000 * 상수값 만큼 돌면 종료된다는 얘기입니다.

1 Like

점근 표기법의 엄밀한 정의는 다음과 같읍니다.

1 Like
  1. 어떤 알고리즘 / 함수 / 프로그램의 성능을 분석한다고 할 때, 해당 알고리즘 / 함수 / 프로그램의 연산량을 정확히 세는 것은 어렵고 노력이 많이 듭니다.
    따라서 O(nlogn), Ω(nlogn)과 같은 점근표기법을 이용해서 연산량의 상한과 하한을 나타내곤 합니다.
    (상한과 하한으로 나타내기 때문에, 가능한 가깝게 한계를 잡아야 의미가 있읍니다.)

  2. 연산량은 입력의 특성(주로 입력의 크기)에 좌우되기 때문에 위의 nlogn과 같이 입력의 특성에 대한 함수 꼴로 연산량을 나타냅니다.

  3. 이러한 점근표기법은 같은 기능을 수행하는 두 함수의 성능을 비교할 때, 프로그램의 입력이 커질 때 프로그램 실행 시간이 얼마나 빠르게 커지는지를 분석할 때 유용합니다.

2 Likes