1. 뭐가 quadratic으로 증가하냐는 건지 모르겠습니다.

2.

맞대요

댓글 감사합니다.

1. 현재 위치가 quadratic으로 증가하냐는 질문이었습니다. 코드에서 #5에 cur

2. 시간 복잡도 식으로 어떻게 계산하신 건가요?

1. 코드를 제대로 까보니 문제의 상황을 그대로 시뮬레이션 하셨더군요.

문제가 원하는 상황 자체가 k에 append되는 값 i가 1씩 증가하다가, 적절한 때부터 1씩 감소하기를 원하는 것이므로, 초기에 cur는 대략 이차함수와 비슷하게 증가합니다.

이후 cur가 증가하는 정도가 선형적으로 줄어드므로, cur의 값은 이제 뒤집어진 이차함수의 형태로 증가할 겁니다.

2. 때문에 시간복잡도는 로그가 아닙니다. 저번 답변때 너무 적은 데이터를 사용해서 계산해서 틀렸네요. 시간복잡도는 O(sqrt(N))입니다. 죄송합니다.

추가로 저거 계산은 별건 아니고, input을 100부터 적당히 1000 정도까지 돌려가면서 loop 횟수를 센 후, 로그함수에 피팅해본 겁니다. 파이썬의 numpy와 scipy를 사용하면 쉽게 할 수 있습니다. 그래프는 파이썬의 matplotlib를 사용해서 그렸습니다.

데이터의 수가 너무 적어서 로그함수가 피팅이 나쁘지 않게 되어버렸네요. 실제 시간복잡도는 루트가 맞습니다. 어째 계수가 이상하다 싶을 때 알아챘어야 했네요...

답변 감사합니다. 모르던게 완벽히 해결되었어요.