こんどの invert は … 最良の場合では … 最悪の場合でO(log z)ステップしかかからないアルゴリズムになりますね
最悪の場合の話の中で最良の場合の計算を使っているような話のつながりになっている？？？ 検討中。
この階段形状内の角部分に z が現れます
f(x,y) = z となる点 (x1,y1), (x2,y2), …(0 <= x_i < m, 0 <= y_i < n) を
スタート点 (0,n) からゴール点 (m,0) まで
(0,n) - (x1,n) - (x1,y1) - (x2,y1) - (x2,y2) …（右に行って下に行くの繰り返し）… (m,0)
と階段状につないでいくと f(x,y) = z になる点 (x,y) は下に行って右に行く曲がり方に現れる。
つまり単調増加関数 f の f(x,y) = z の解集合 (x,y) と階段の形状は一対一対応する。
log A(m,n) = Ω(m * log(1+n/m) + n * log(1+m/n))
スターリングの公式
n! 〜 √(2πn) * n^n/e^nを使う。
A(m,n) = (m+n)!/(m! * n!)
〜 √(2π(m+n)) * (m+n)^(m+n)/e^(m+n) / (√(2πm) m^m/e^m * √(2πn) n^n/e^n)
= √((m+n)/(2πmn)) * (m+n)^(m+n) / (m^m * n^n)
= √((1/m + 1/n)/(2π)) * (m+n)^m / m^m * (m+n)^n / n^n
= √((1/m + 1/n)/(2π)) * (1+n/m)^m * (1+m/n)^n
log を取ると
log A(m,n) 〜 1/2 * log((1/m + 1/n)/(2π)) + m * log(1+n/m) + n * log(1+m/n)
= Ω(m * log(1+n/m) + n * log(1+m/n))