[일반] 이런 문제는 수학적으로 엄밀하게 어떻게 증명함?

[익명(118.235)]

일단 최솟값이 되는 값을 아는 것 자체는 매우 쉬운데

그게 왜 최솟값인지를 증명하는 것.

즉

어떠한 다른 경주방식을 사용해도

저 횟수보다 작아질수없다를

"엄밀하게" 보이는 거는 도통 갈피가 얀잡히는데

이런건 엄밀하게 증명 대체 어떻게 함?

- dc official App

[연쵸(solstice4649)]

고1때 봤던거같은데 7번인가? - dc App

[ㅆㅅ(siiot)]

최악의 경우와 최선의 경우를 가정해서 상한과 하한의 간격을 줄여나가는 방법이 많이 쓰임

[익명(fourth8861)]

트리를 생각해서 정렬에서의 하한을 잡으면 됨

[익명(223.38)]

대충 멋진생각했다고 생각했는데 엄밀하지 않다고 털리고 좃나 까였나보네 ㅋㅋ

[수갤러 2(118.235)]

딱봐도 까인글이 아닌데

[익명(wireless6882)]

Lower bound info theory 이용하면 될듯?