CLRS (Introduction To Alglorithms, 3rd edition) 책을 읽고 있는데 마스터 정리 증명에 오류가있는 것 같습니다. 104 페이지에서 증명을 모든 정수로 확장하기 위해 잘못된 것처럼 보이는 하나의 방정식을 사용합니다. 책에서 다음과 같이 말했습니다.
첫 번째 목표는 nk가 상수가되도록 깊이 k를 결정하는 것입니다. 부등식 [x] <= x + 1을 사용하여
[X] 여기서 x의 천장을 의미하며, 이는 명백하다 [x] < x+1하지 [x] <= x+1. 게다가 54쪽에 또 다른 불평등이 있습니다.
x -1 < flooring(x) <= x <= ceiling(x) < x+1
누구든지 이것을 명확히하는데 도움을 줄 수 있습니다. 왜 그들이 갈등입니까? 이 부등식이 정확하지 않으면 전체 증명이 정확하지 않습니다.
두 가지 경우로 분할 :
[x] > x---> [x] < x+1(사소하고 동의한다고 생각합니다)[x] = x---> [x]+1 = x + 1--->[x] < x+1마찬가지로 x-1 < floor(x), 두 경우로 분할합니다.
floor(x) < x ---> floor(x) > x-1floor(x) = x---> floor(x) - 1 = x - 1--->floor(x) > x-1그래서, 마지막 방정식에서-모든 것은 남았습니다 floor(x)<=c<=ceil(x)-이것은 그들의 정의에서 거의 직접적으로 그리고 위의 두 주장에서 우리는 그것을 얻습니다 :
x -1 < flooring(x) <= x <= ceiling(x) < x+1
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다