オッズの連続配列で数値の2乗を求める

Question

3から始まる連続した奇数配列があります。So x = {3,4,5,6,7,8,9,10,11,12,13 ...}。 数字nの正方形がどのインデックスにあるかを素早く見つける方法があるのだろうかと思います。したがって、nが5の場合、配列内に25がどこにあるかを探しています。今、私は現在のインデックスに追加する（（n）*（n - 1））を持っています。何か速いですか？

Answer 1

あなたの配列は、連続した数字で作られており、それがインデックスiで、我々はa[i]=i+3のでi=a[i]-3を持っているので、それは、3と違い1と第一の要素で数学的計算の進行をなすこのため、並べ替えています。

だから nsqrが n*nなりましょう nの広場のインデックスを見つけるために、nsqrインデックスは単に nsqr-3あり、それは O(1)アルゴリズムです。

我々はa0で開始し、我々は(nsqr-a0)/dを行うnの二乗がどこにあるかを見つけるために、dによって異なる連続でソートされた数字を持っている時はいつでも、それが一般的なようにします。