Thingmemo

EXECUTABLE ARCHIVE

アルゴリズム実行室

入力を変え、処理を実行し、結果と計算誤差を確かめるための作業台です。 すべての処理はブラウザ内の型付き関数として実行されます。

244件の実装

組合せ

パスカルの三角形

直前の行の隣接する2値から二項係数の三角形を生成します。

TIME
O(n²)
SPACE
O(n²)

上限: 1〜20段

確率・統計

ポアソン分布

平均発生回数λから各回数の確率と累積確率を計算します。

TIME
O(k)
SPACE
O(k)

上限: λは0〜50、kは0〜100

線形代数

QR分解

Householder反射で実正方行列を直交行列Qと上三角行列Rへ分解します。

TIME
O(n³)
SPACE
O(n²)

上限: 2×2〜4×4、各要素の絶対値は1,000,000以下

線形代数

QR法

対称行列へQR分解を反復適用し、固有値へ収束する対角成分を求めます。

TIME
O(i n³)
SPACE
O(n²)

上限: 2×2〜4×4、最大500反復

乱数

rand()

整数演算だけの線形合同法で、seedから再現可能な疑似乱数列を生成します。

TIME
O(k)
SPACE
O(k)

上限: seedは0〜2³¹−1、10,000個以下

数値解析

リーマンのゼータ関数

s>1で収束するディリクレ級数と打切り誤差上界を計算します。

TIME
O(N)
SPACE
O(1)

上限: 1.01≤s≤20、100,000項以下

ソート

シェルソート

間隔を半減する挿入操作で数値列を整列し、移動履歴を返します。

TIME
O(n²)
SPACE
O(n)

上限: 10,000要素以下、履歴300件まで

フラクタル

シェルピンスキー曲線

L-systemを展開し、シェルピンスキー矢じり曲線の折れ線座標を生成します。

TIME
O(3ⁿ)
SPACE
O(3ⁿ)

上限: 次数0〜9

フラクタル

シェルピンスキー三角形

三角形を3分割する再帰から、残る三角形群の座標を生成します。

TIME
O(3ⁿ)
SPACE
O(3ⁿ)

上限: 次数0〜8

組合せ

スターリング数

第1種・第2種スターリング数を漸化式とBigIntで厳密計算します。

TIME
O(nk)
SPACE
O(nk)

上限: 0≤k≤n≤50

線形代数

SWEEP演算子法

対称行列の指定ピボットをSWEEP変換し、各段階の行列を返します。

TIME
O(p n²)
SPACE
O(p n²)

上限: 1×1〜8×8

構文解析

TeX

TeX数式のコマンド・グループ・上下付きを字句解析し、構造を検証します。

TIME
O(n)
SPACE
O(n)

上限: 2,000文字以下

確率・統計

t分布

自由度とt値から密度と正則化不完全ベータ関数による累積確率を求めます。

TIME
O(i)
SPACE
O(1)

上限: 自由度1〜200、|t|≤20

確率・統計

ワイブル分布

形状・尺度母数からワイブル分布の密度、累積確率、生存確率を求めます。

TIME
O(1)
SPACE
O(1)

上限: 0≤x≤10,000、母数は正

乱数

Wichmann-Hill乱数

3本の合同列を合成して再現可能なWichmann–Hill疑似乱数を生成します。

TIME
O(k)
SPACE
O(k)

上限: 各seedは法未満、10,000個以下

基礎操作

値の交換

元配列を変更せず、指定した2つの添字の値を交換した配列を返します。

TIME
O(n)
SPACE
O(n)

上限: 10,000要素以下

基礎操作

アルゴリズム

有限・明確・決定的な手続きの例として、最大公約数計算を段階表示します。

TIME
O(log n)
SPACE
O(log n)

上限: 1〜1,000,000,000の整数

セキュリティ

暗号

独自暗号を使わず、標準Web Crypto APIでSHA-256ダイジェストを計算します。

TIME
O(n)
SPACE
O(n)

上限: 入力1MiB以下

組合せ

安定結婚問題

Gale–Shapley法で、どの2人にも相互乗換えの動機がない対応を構成します。

TIME
O(n²)
SPACE
O(n²)

上限: 各グループ100人以下

組合せ

異性体の問題

次数4以下の非同型自由木として、小さなアルカンの炭素骨格を列挙します。

TIME
指数時間
SPACE
指数空間

上限: 炭素数1〜10

確率・統計

因子分析

相関行列へべき乗法とデフレーションを適用し、因子負荷量を推定します。

TIME
O(f i n²)
SPACE
O(n²)

上限: 2×2〜8×8、因子数n−1以下

数論

エジプト分数

真分数をFibonacci–Sylvester貪欲法で異なる単位分数の和へ分解します。

TIME
O(k)
SPACE
O(k)

上限: 分母1,000,000以下、100項まで

数値解析

円周率

Nilakantha級数を反復し、円周率近似と絶対誤差を表示します。

TIME
O(n)
SPACE
O(1)

上限: 1〜100,000反復

計算機基礎

エンディアンネス

ArrayBufferのバイト配置を観察し、実行環境のエンディアンを検出します。

TIME
O(1)
SPACE
O(1)

上限: 入力なし

最適化

黄金分割法

単峰な二次式の探索区間を黄金比で縮小し、最小点を求めます。

TIME
O(log(1/ε))
SPACE
O(log(1/ε))

上限: 区間端点の絶対値1,000,000以下、500反復

確率・統計

回帰分析

最小二乗法で単回帰直線、予測値、残差、決定係数を計算します。

TIME
O(n)
SPACE
O(n)

上限: 2〜100標本

数論

階乗進法

10進整数を各桁の基数が階乗で増える階乗進表現へ変換します。

TIME
O(log n)
SPACE
O(log n)

上限: 0〜20!−1

力学系

カオスのアトラクタ

ロジスティック写像xₙ₊₁=r xₙ(1−xₙ)を反復し、軌道を可視化します。

TIME
O(n)
SPACE
O(n)

上限: 0≤r≤4、10,000反復以下

特殊関数

ガンマ関数

Lanczos近似と反射公式で、整数の階乗を拡張するガンマ関数を評価します。

TIME
O(1)
SPACE
O(1)

上限: −50<x≤171、非正整数を除く

確率・統計

ガンマ分布

形状・尺度母数から密度と正則化不完全ガンマ関数による累積確率を求めます。

TIME
O(i)
SPACE
O(1)

上限: 0≤x≤10,000、母数は正

データ構造

木

二分木を前順・間順・後順・幅優先のいずれかで走査します。

TIME
O(n)
SPACE
O(n)

上限: 10,000ノード以下

数値解析

機械イプシロン

1と区別できる最小の倍精度浮動小数点差を半減法で実測します。

TIME
O(p)
SPACE
O(1)

上限: IEEE 754倍精度

確率・統計

幾何分布

最初の成功までの失敗回数について、確率質量・累積確率・平均・分散を求めます。

TIME
O(1)
SPACE
O(1)

上限: 0≤k≤1,000、0<p≤1

数論

基数変換

BigIntの位取り演算で、2〜36進の整数文字列を別の基数へ変換します。

TIME
O(n²)
SPACE
O(n)

上限: 2〜36進、64桁以下

線形代数

逆行列

部分ピボット付きGauss–Jordan消去で正方行列の逆行列を求めます。

TIME
O(n³)
SPACE
O(n²)

上限: 1×1〜8×8

特殊関数

逆三角関数

同じ入力から逆正弦・逆余弦・逆正接をラジアンで計算します。

TIME
O(1)
SPACE
O(1)

上限: −1≤x≤1

ソート

逆写像ソート

重複しない整数を値から元位置へ逆引きし、整列順と元添字を返します。

TIME
O(n log n)
SPACE
O(n+r)

上限: 10,000要素以下、値域100,000以下

特殊関数

逆双曲線関数

逆双曲線正弦と、定義域内の逆双曲線余弦・正接を計算します。

TIME
O(1)
SPACE
O(1)

上限: 有限の実数

集合

共通要素

2配列の積集合を、重複なし・左配列での初出順に返します。

TIME
O(n+m)
SPACE
O(n+m)

上限: 各10,000要素以下

線形代数

行列

行列の形状、転置、トレースと、同型行列があれば行列和を計算します。

TIME
O(rc)
SPACE
O(rc)

上限: 最大16×16

線形代数

行列積

内側の次元が一致する2行列を三重ループで乗算します。

TIME
O(rck)
SPACE
O(rc)

上限: 各次元16以下

ソート

クイックソート

中央要素をピボットにした反復分割で数値列を整列し、分割履歴を返します。

TIME
平均O(n log n)
SPACE
O(n)

上限: 10,000要素以下、履歴300件まで

計算幾何

区間の包含関係

閉区間同士を全比較し、どの区間がどの区間を包含するか列挙します。

TIME
O(n²)
SPACE
O(n²)

上限: 100区間以下

組合せ

組合せの数

BigIntによる乗除算で、n個からk個を選ぶ組合せ数を厳密に求めます。

TIME
O(min(k, n−k))
SPACE
O(1)

上限: 0≤k≤n≤10,000

組合せ

組合せの生成

入力位置の辞書順で、k要素の組合せをすべて生成します。

TIME
O(C(n,k) k)
SPACE
O(C(n,k) k)

上限: 要素数1,000以下、0≤k≤n、出力100,000件以下

グラフ

グラフ

重み付き隣接リストを検証し、幅優先探索または深さ優先探索の訪問順を求めます。

TIME
O(V+E)
SPACE
O(V+E)

上限: 頂点1〜1,000、辺10,000本以下

計算幾何

グラフィックス

Bresenham法で整数格子上の線分をラスタライズし、画素列を生成します。

TIME
O(max(|Δx|,|Δy|))
SPACE
O(p)

上限: 各座標−1,000,000〜1,000,000、画素数10,000以下

数値解析

桁落ち

√(x+1)−√xと有理化した安定式を比較して桁落ちを示します。

TIME
O(1)
SPACE
O(1)

上限: 1≤x≤10²⁰

数論

原始根

有界な素数を検証し、その法におけるすべての原始根を列挙します。

TIME
O(p √p log p)
SPACE
O(p)

上限: 素数2〜100,000

構文解析

後置記法

中置算術式を後置記法へ変換し、スタックで安全に評価します。

TIME
O(n)
SPACE
O(n)

上限: 式1〜1,000文字、512トークン以下

数論

合同式

拡張ユークリッド互除法でa×x≡b (mod m)の全解を正準剰余として求めます。

TIME
O(log m + g log m)
SPACE
O(g)

上限: |a|,|b|≤10⁹、1≤m≤100,000

線形代数

5重対角な連立方程式

5本の対角帯から係数行列を組み、部分ピボット付き消去で解きます。

TIME
O(n³)
SPACE
O(n²)

上限: 1≤n≤32、各帯の長さを厳密に一致

確率・統計

五数要約

標本を整列し、最小値・四分位数・中央値・最大値を線形補間で求めます。

TIME
O(n log n)
SPACE
O(n)

上限: 標本数1〜10,000

動的計画法

小銭の払い方

額面ごとの一次元DPで、指定額を作る順序を区別しない硬貨の組合せ数を求めます。

TIME
O(ad)
SPACE
O(a)

上限: 金額0〜10,000、重複なしの額面100個以下

線形代数

固有値・固有ベクトル・対角化

Jacobi回転法で実対称行列の固有値・直交固有ベクトルと対角化を計算します。

TIME
O(i n²)
SPACE
O(n²)

上限: 対称な1×1〜32×32、許容誤差10⁻¹⁵〜10⁻³、最大100,000反復

構文解析

再帰的下向き構文解析

四則演算・括弧・単項マイナスの式を再帰下降で構文木へ解析し評価します。

TIME
O(n)
SPACE
O(n)

上限: 式1〜1,000文字、512トークン以下

計算機基礎

最上位ビット

非負の安全整数について、最上位に立つビットの添字と値を返します。

TIME
O(1)
SPACE
O(1)

上限: 0〜Number.MAX_SAFE_INTEGERの整数

数論

最小公倍数

最大公約数を用いた除算先行の積で、2整数の安全な最小公倍数を求めます。

TIME
O(log min(|a|,|b|))
SPACE
O(1)

上限: 各値は安全な整数、結果も安全な整数

数論

最大公約数

ユークリッドの互除法で、符号を除いた2つの安全整数の最大公約数を求めます。

TIME
O(log min(|a|,|b|))
SPACE
O(1)

上限: 各値は−Number.MAX_SAFE_INTEGER〜Number.MAX_SAFE_INTEGERの整数

基礎操作

最大値・最小値

数列を一走査して最大値・最小値とそれぞれの最初の添字を求めます。

TIME
O(n)
SPACE
O(1)

上限: 有限数の要素1〜10,000個

グラフ

最短路問題

負でない重みの隣接リストにダイクストラ法を適用し、始点から終点までの最短路を求めます。

TIME
O(V²+E)
SPACE
O(V+E)

上限: 頂点1〜1,000、辺10,000本以下、重みと求める経路距離は有限かつ非負

特殊関数

三角関数

ラジアン角から正弦・余弦・定義される場合の正接を計算します。

TIME
O(1)
SPACE
O(1)

上限: −10¹²≤角度≤10¹²

数値解析

三角関数による補間

等間隔の周期標本から有限DFT係数を求め、任意点を三角補間します。

TIME
O(n²)
SPACE
O(n)

上限: 有限数の標本2〜128個、|x|≤1,000,000

確率・統計

三角分布

最小値・最頻値・最大値から三角分布の密度、累積確率、平均、分散を求めます。

TIME
O(1)
SPACE
O(1)

上限: 有限の実数、最小値<最大値かつ最小値≤最頻値≤最大値

計算幾何

3次元グラフ

指定関数を矩形格子で評価し、3次元曲面の点列と格子を生成します。

TIME
O(rc)
SPACE
O(rc)

上限: 各軸の端点・幅は有限で最小<最大、行・列2〜100、格子点10,000以下

数値解析

3次方程式

係数を正規化して実係数3次方程式を解き、相異なる実根・元の式の残差・正規化残差を返します。

TIME
O(1)
SPACE
O(1)

上限: 有限係数、a≠0、|a|/max(|a|,|b|,|c|,|d|)>64ε

線形代数

3重対角化

Householder反射の相似変換で実対称行列を3重対角行列へ変換します。

TIME
O(n⁴)
SPACE
O(n²)

上限: 対称な1×1〜32×32

線形代数

3重対角な連立方程式

3本の対角帯に前進消去・後退代入を適用して連立方程式を解きます。

TIME
O(n)
SPACE
O(n)

上限: 1≤n≤32、各帯の長さを厳密に一致、特異でない行列

圧縮

算術圧縮

入力文字列の頻度モデルからBigIntの有理区間を作り、可逆な算術符号化を行います。

TIME
O(n²)
SPACE
O(n)

上限: 入力64文字以下、復号用整数は1,000桁以下

構文解析

式の評価

安全に字句解析した四則演算式を後置記法へ変換して評価します。

TIME
O(n)
SPACE
O(n)

上限: 式1〜1,000文字、512トークン以下

探索

自己組織化探索

線形探索で見つけた要素を先頭へ移動し、更新後の配列と比較回数を返します。

TIME
O(n)
SPACE
O(n)

上限: 配列要素10,000個以下

数値解析

四捨五入

指数表記による桁移動で、同点を0から遠い側へ丸める10進四捨五入を行います。

TIME
O(1)
SPACE
O(1)

上限: 値は有限、−12≤d≤12、丸め計算結果が有限

基礎操作

辞書式順序

数値または文字列の2列を先頭から比較し、辞書式の大小を返します。

TIME
O(min(n,m))
SPACE
O(1)

上限: 各列10,000要素以下、値は有限数または文字列

特殊関数

指数関数

Math.expで指数関数eˣを有限の倍精度範囲で評価します。

TIME
O(1)
SPACE
O(1)

上限: −709≤x≤709

確率・統計

指数分布

率母数から指数分布の密度、累積確率、生存確率、平均、分散を求めます。

TIME
O(1)
SPACE
O(1)

上限: xは有限、10⁻⁹≤λ≤10⁶

特殊関数

自然対数の底

eの級数Σ1/k!を指定項数まで加算し、Math.Eとの差を表示します。

TIME
O(n)
SPACE
O(1)

上限: 1〜50項

数論

実数

10進表記またはpi・π・eを解析し、有限実数としての分類と性質を返します。

TIME
O(n)
SPACE
O(1)

上限: 空白なしの1〜100文字、有効な10進表記・pi・π・e

文字コード

シフトJISコード

ASCIIとひらがなの対応部分集合について、Shift JISの符号化・検証・復号を行います。

TIME
O(n)
SPACE
O(n)

上限: ASCII・ひらがなのみ、入力・出力とも1,024バイト以下

確率・統計

主成分分析

中心化データの共分散行列を固有分解し、主成分・寄与率・主成分得点を求めます。

TIME
O(i d² + sd²)
SPACE
O(sd+d²)

上限: 標本2〜1,000、変数1〜32、主成分数1〜d

フラクタル

樹木曲線

二分再帰で枝分かれする樹木曲線の線分と根から葉への折れ線を生成します。

TIME
O(2ᵈ)
SPACE
O(2ᵈ)

上限: 深さ0〜9、長さ10⁻⁹〜10⁶、縮小率0.1〜0.95

探索

順位づけ

数値列を安定に整列し、同値に同順位を与える競技順位を返します。

TIME
O(n log n)
SPACE
O(n)

上限: 有限数の要素10,000個以下、ascendingまたはdescending

組合せ

順列

0からn−1の順列について、辞書式での0始まり順位とその逆変換を計算します。

TIME
O(n²)
SPACE
O(n)

上限: 順列サイズ0〜1,000、順位は0以上n!未満のBigInt

組合せ

順列生成

入力位置の辞書順で、すべての順列を生成します。

TIME
O(n! n)
SPACE
O(n! n)

上限: 要素数1,000以下、順列数は出力100,000件以下

線形代数

条件数

部分ピボット付きGauss–Jordan法で逆行列を求め、無限大ノルム条件数を計算します。

TIME
O(n³)
SPACE
O(n²)

上限: 有限要素の1×1〜32×32正方行列、数値的に特異でないこと

数論

小数の循環節

BigIntの長除法で有理数の非循環部と循環節を厳密に分離します。

TIME
O(k·M(d))
SPACE
O(kd)

上限: 分子・分母は各4,096桁以下のBigInt、分母≠0、0≤最大生成桁数≤10,000

数値解析

常微分方程式

スカラー初期値問題を固定刻みEuler法または4次Runge–Kutta法で解き、半刻みとの差も評価します。

TIME
O(s)
SPACE
O(s)

上限: 初期x・初期y・目標xは−10⁹〜10⁹、刻み10⁻¹²〜10⁹、1〜10,000ステップ、許容誤差10⁻¹⁵〜1

数値解析

情報落ち

大きさの異なる浮動小数点数の加減算で小さい値が失われる現象を実測します。

TIME
O(1)
SPACE
O(1)

上限: xとsmallはそれぞれ−10³⁰⁰〜10³⁰⁰の有限数

グラフ

推移的閉包

Warshall法で有向グラフの隣接行列から到達可能性の推移的閉包を求めます。

TIME
O(V³)
SPACE
O(V²)

上限: 要素が0または1の1×1〜200×200正方隣接行列、履歴256件まで

数値解析

スプライン補間

狭義単調な標本点から自然3次スプライン係数を構成し、区間内の値を評価します。

TIME
構築O(n)、評価O(log n)
SPACE
O(n)

上限: 有限数のx・yを各2〜1,000個、同数かつxは狭義単調増加、評価点は補間区間内

確率・統計

正規分布

正規分布の密度とAbramowitz–Stegunのerf近似による累積確率を計算します。

TIME
O(1)
SPACE
O(1)

上限: xと平均は有限数、標準偏差は10⁻³⁰⁰〜10³⁰⁰

特殊関数

正弦積分

適応Simpson法の有界スタックでsin(t)/tを0からxまで数値積分します。

TIME
O(s)
SPACE
O(s)

上限: −10⁶≤x≤10⁶、許容誤差10⁻¹⁵〜10⁻²、最大分割数1〜100,000

数論

整数

2〜36進の符号付き整数文字列をNumberを介さずBigIntへ厳密変換します。

TIME
O(d²)
SPACE
O(d)

上限: 基数2〜36、符号を含めて1〜4,097文字、数字部分は1文字以上

数論

整数の除算

BigIntで切捨て・床・Euclidの3方式の商と余りを厳密に求めます。

TIME
O(M(d))
SPACE
O(d)

上限: 被除数・除数は各4,096桁以下のBigInt、除数≠0

数論

整数の積

安全な整数・BigInt・10進整数文字列の因子をBigIntで厳密に乗算します。

TIME
O(f·M(D))
SPACE
O(D)

上限: 因子1,000個以下、BigIntは各4,096桁以下、10進文字列は符号込み4,097文字以下、Numberは安全な整数、積は10,000桁以下

ソート

整列

反復型の安定マージソートで、指定比較関数に従って配列を整列します。

TIME
O(n log n)
SPACE
O(n)

上限: 10,000要素以下、比較関数は有限数を返すこと、履歴256件まで

最適化

線形計画法

非負の2変数と有界件数の線形制約について境界交点を列挙し、最適・実行不能・非有界を判定します。

TIME
最悪O(m⁴)
SPACE
O(m²)

上限: 2変数、制約0〜60件、目的・制約係数と境界は−10⁹〜10⁹、制約名100文字以下

乱数

線形合同法

BigIntの漸化式xₙ₊₁=(a xₙ+c) mod mで再現可能な整数疑似乱数列を生成します。

TIME
O(k·M(d))
SPACE
O(kd)

上限: seed・a・c・mは各100桁以下のBigInt、m>0、生成数0〜10,000

探索

選択

末尾ピボットのQuickselectで数列の0始まりk番目に小さい値を選択します。

TIME
平均O(n)、最悪O(n²)
SPACE
O(n)

上限: 有限数を1〜10,000個、0≤k<n、履歴256件まで

ソート

選択ソート

未整列部分の最小値を順に選んで交換し、比較・交換履歴と整列結果を返します。

TIME
O(n²)
SPACE
O(n)

上限: 有限数を10,000個以下、履歴256件まで、配列スナップショットは128要素以下

数論

素因数分解

2と奇数候補による試し割りで整数を素数の冪の積へ分解します。

TIME
O(√n)
SPACE
O(log n)

上限: 2≤n≤1,000,000,000,000の整数

確率・統計

相関係数

同じ長さの2標本からPearsonの積率相関係数と標本共分散を計算します。

TIME
O(n)
SPACE
O(n)

上限: 有限数の標本を各2〜10,000個、同数で両標本の分散が正、計算結果が有限

特殊関数

双曲線関数

実数xの双曲線正弦・余弦・正接を標準数学関数で評価します。

TIME
O(1)
SPACE
O(1)

上限: −710≤x≤710、sinhとcoshが有限になること

ソート

挿入ソート

各要素を整列済み部分の適切な位置へ挿入し、安定に昇順整列します。

TIME
平均・最悪O(n²)、最良O(n)
SPACE
O(n)

上限: 有限数を10,000個以下、履歴256件まで、配列スナップショットは128要素以下

数論

素数

安全な非負整数を固定基底の決定的Miller–Rabin法で素数判定します。

TIME
O(log³ n)
SPACE
O(log n)

上限: 0〜Number.MAX_SAFE_INTEGERの整数

数論

素数の Lucas テスト

素数指数pを前提とするLucas–Lehmer法だけで、Mersenne数2ᵖ−1の素数性を厳密判定します。

TIME
O(p·M(p))
SPACE
O(p²)

上限: 指数pは2〜127の整数。pが素数でない場合は前提不成立を返す

特殊関数

対数

底の変換公式log(value)/log(base)で任意の有効な底の対数を計算します。

TIME
O(1)
SPACE
O(1)

上限: valueは正の有限数、baseは正かつ1以外の有限数

数値解析

多項式の計算

最高次から並ぶ係数列をHorner法で評価し、各積和の過程を返します。

TIME
O(n)
SPACE
O(n)

上限: 有限係数を1〜10,000個、−10¹⁰⁰≤x≤10¹⁰⁰、すべての中間結果が有限

グラフ

縦形探索

明示スタックによる深さ優先探索で、開始頂点からの訪問順と探索木を求めます。

TIME
O(V+E)
SPACE
O(V)

上限: 隣接リストの頂点1〜1,000、辺10,000本以下、開始頂点は範囲内

数論

多倍長演算

符号付き10進整数文字列2個の和・差・積と、除数が非零なら商・余りをBigIntで厳密計算します。

TIME
O(M(d))
SPACE
O(d)

上限: 各入力は符号込み1〜4,097文字の10進整数文字列、積は10,000桁以下

確率・統計

多変量データ

標本行列の変数別平均・標本共分散行列・標準偏差・相関行列を計算します。

TIME
O(sd²)
SPACE
O(sd+d²)

上限: 有限要素の2〜10,000標本、1〜32変数、要約統計量が有限

乱数

単位球上のランダムな点

32ビットseedの疑似乱数とMarsaglia棄却法で単位球面上の点を再現可能に生成します。

TIME
期待O(k)
SPACE
O(k)

上限: seedは0〜4,294,967,295の整数、生成点数0〜10,000

探索

探索

昇順を検証した配列を比較関数による二分探索で検索し、比較位置を返します。

TIME
O(n)（整列検証込み、探索はO(log n)）
SPACE
O(n)

上限: 10,000要素以下、昇順、比較関数は有限数を返すこと

計算機基礎

チェックサム

UTF-8バイト列のCRC-32/ISO-HDLCを計算し、任意の8桁16進期待値と照合します。

TIME
O(b)
SPACE
O(1)

上限: 入力はUTF-8で1,048,576バイト以下、期待値を指定する場合は8桁の16進数

組合せ

置換の符号

Fenwick木で0〜n−1の順列の転倒数と偶奇を求め、置換の符号を返します。

TIME
O(n log n)
SPACE
O(n)

上限: 0〜10,000要素、各値は0〜n−1を重複なく1回ずつ

探索

逐次探索

配列を先頭から等価判定し、最初に一致した添字と探索位置を返します。

TIME
O(n)
SPACE
O(n)

上限: 10,000要素以下、等価関数を指定する場合は関数であること

数値解析

直角三角形の斜辺の長さ

Math.hypotで桁あふれ・桁あふれ不足を避けながら2辺から斜辺長を計算します。

TIME
O(1)
SPACE
O(1)

上限: 2辺は有限数、計算される斜辺長も有限

圧縮

データ圧縮

Unicode文字列を連長圧縮し、サイズ情報を検証して可逆に展開します。

TIME
O(n)
SPACE
O(n)

上限: 入力・展開結果はUTF-16で10,000コード単位以下、圧縮データの原バイト数40,000以下・符号化バイト数60,000以下、各run数1〜10,000

計算幾何

等高線

有限値の矩形格子へMarching Squares法を適用し、指定レベルの等高線分を生成します。

TIME
O(rc)
SPACE
O(s)

上限: 有限要素の2×2〜128×128格子、有限のlevel、最大線分数1〜10,000

動的計画法

動的計画法

右または下へ進む格子経路の最小コストを表形式DPで厳密に求め、経路を復元します。

TIME
O(rc)
SPACE
O(rc)

上限: 有限要素の1〜100行・1〜100列、総セル数10,000以下、累積コストが有限

グラフ

トポロジカル・ソーティング

Kahn法で有向非巡回グラフのトポロジカル順序を求め、閉路があれば明示的に失敗します。

TIME
O(V+E)
SPACE
O(V+E)

上限: 隣接リストの頂点1〜1,000、辺10,000本以下、履歴256件まで、閉路がないこと

フラクタル

ドラゴンカーブ

折り目列を反転・反転符号で展開し、Heighwayドラゴンの整数格子点を生成します。

TIME
O(2ᵈ)
SPACE
O(2ᵈ)

上限: 次数0〜16の整数

線形代数

内積

同次元の2実ベクトルの要素積を一走査で加算し、内積を計算します。

TIME
O(n)
SPACE
O(n)

上限: 有限要素を各1〜10,000個、同次元、すべての累積和が有限

最適化

ナップザックの問題

0/1ナップザックを容量DPで厳密に解き、選択品を復元します。一般の最適化問題はNP困難です。

TIME
O(nC)（擬多項式時間）
SPACE
O(nC)

上限: 品物0〜200件、0≤容量≤5,000、各重量は0〜5,000の整数、価値は−10⁹〜10⁹の有限数

確率・統計

２項分布

Lanczos対数ガンマで確率質量を安定に評価し、最頻値から比を更新して下側累積確率を求めます。

TIME
O(n)
SPACE
O(1)

上限: 0≤k≤n≤100,000、0≤成功確率≤1。倍精度計算で端の質量は0へアンダーフローし得ます

探索

２次元の探索

各行・各列が昇順の矩形行列を右上から左または下へ進み、探索経路と位置を返します。

TIME
O(r+c)
SPACE
O(r+c)

上限: 有限要素の1×1〜256×256矩形行列、各行・各列は昇順

数値解析

２次方程式

最大係数で正規化し、桁落ちを抑えるq形式で実根または複素根を求め、退化した一次式も扱います。

TIME
O(1)
SPACE
O(1)

上限: 係数は有限数。a=0の一次式・恒等式・矛盾式を明示し、有限結果を要求

データ構造

２分木

レベル順配列から親のないノードを拒否して二分木を構築し、前順・間順・後順・幅優先順を反復走査します。

TIME
O(n)
SPACE
O(n)

上限: レベル順配列は2,047要素以下。共有ノード・循環・到達不能ノードを拒否

探索

２分探索

昇順の有限数列で探索区間を半分ずつ狭め、一致位置と各比較後の区間遷移を返します。

TIME
O(log n)
SPACE
O(log n)

上限: 昇順の有限数を10,000要素以下

データ構造

２分探索木

挿入・探索・削除を順に実行し、重複をcount・ignore・rejectから選んで探索路と有界なスナップショットを返します。

TIME
最悪O(mn)
SPACE
最悪O(mn)

上限: 操作・ノードは各2,047以下、履歴256件、スナップショット総ノード10,000以下

数値解析

２分法

cubicまたはcos-minus-xの同じ安全な式族について、符号が異なる区間を二分して根・残差・履歴・停止理由を返します。

TIME
O(i)
SPACE
O(i)

上限: 端点は−10⁶〜10⁶、許容誤差10⁻¹⁵〜1、1〜1,000反復（既定10⁻¹⁰・100回）

確率・統計

２変量正規分布

平均・標準偏差・相関係数から標準化値と2変量正規分布の同時確率密度を閉形式で計算します。

TIME
O(1)
SPACE
O(1)

上限: 入力と平均は有限、標準偏差10⁻¹⁵⁰〜10¹⁵⁰、|相関係数|<1、結果は有限

数論

秤の問題

整数を平衡3進数へ変換し、3の冪の分銅を左右どちらへ置くかと検算結果を返します。

TIME
O(log |t|)
SPACE
O(log |t|)

上限: −1,000,000,000〜1,000,000,000の整数

数値解析

はさみうち法

cubicまたはcos-minus-xの同じ安全な式族について、端点の関数値による線形補間で符号区間を更新します。

TIME
O(i)
SPACE
O(i)

上限: 端点は−10⁶〜10⁶、許容誤差10⁻¹⁵〜1、1〜1,000反復（既定10⁻¹⁰・100回）

データ構造

ハッシュ法

整数または文字列キーをFNV-1a系ハッシュと線形探索の開番地法で挿入・探索・削除し、墓石と探索履歴を返します。

TIME
最悪O(mc)
SPACE
O(c+m)

上限: 容量2〜4,096、操作10,000件以下、履歴256件、文字列キー256文字以下、整数キーは安全整数、負荷率上限0超1以下

ソート

バブルソート

隣接要素を比較交換し、交換のない周回で早期終了して比較数・交換数・有界な遷移履歴を返します。

TIME
最悪O(n²)、最良O(n)
SPACE
O(n)

上限: 有限数2,000要素以下、履歴256件、スナップショットは128要素以下でのみ保存

探索

番人

対象値を配列末尾へ一時的な番人として追加して逐次探索し、元配列の復元と比較添字を返します。

TIME
O(n)
SPACE
O(n)

上限: 10,000要素以下。等価関数を指定する場合は関数であること

ソート

ヒープソート

配列内に最大ヒープを構築して末尾へ最大値を移し、比較数・交換数・有界な遷移履歴を返します。

TIME
O(n log n)
SPACE
O(n)

上限: 有限数10,000要素以下、履歴256件、スナップショットは128要素以下でのみ保存

計算機基礎

ビットごとの排他的論理和

非負整数をBigIntへ検証変換して排他的論理和を行い、幅を揃えた2進表現と10進結果を返します。

TIME
O(w)
SPACE
O(w)

上限: 数値は0〜2³²−1の整数、10進文字列は256ビット未満かつ78桁以下

グラフ

一筆書き

無向多重グラフを検証し、Hierholzer法で全辺を一度ずつ通るオイラー路または閉路と有界な遷移を返します。

TIME
O(V+E)
SPACE
O(V+E)

上限: 頂点1〜2,047、辺5,000本以下、辺を持つ部分は連結、奇数次数頂点は0個または2個、履歴256件

データ構造

ひも付き２分木

二分木の空リンクを間順の前任・後任へのひもに変換し、再帰や補助スタックなしの間順走査を検証します。

TIME
O(n)
SPACE
O(n)

上限: ノード2,047個以下。共有・循環・到達不能ノードと不正なひもを拒否

特殊関数

不完全ガンマ関数

級数またはLentz連分数で正則化下側不完全ガンマ関数を求め、倍精度の有界近似として誤差指標・反復数・収束状態・方式を返します。

TIME
O(i)
SPACE
O(1)

上限: 10⁻¹²≤a≤10⁵、0≤x≤10⁶、許容誤差10⁻¹⁶〜10⁻²、1〜10,000反復（既定10⁻¹⁴・1,000回）

特殊関数

不完全ベータ関数

対称性を選んだ連分数で正則化不完全ベータ関数を求め、倍精度の有界近似として誤差指標・反復数・収束状態を返します。

TIME
O(i)
SPACE
O(1)

上限: 10⁻¹²≤a,b≤10⁵、0≤x≤1、許容誤差10⁻¹⁶〜10⁻²、1〜10,000反復（既定10⁻¹⁴・1,000回）

数値解析

複素数

有限な実部・虚部を持つ2複素数の加減乗除を計算し、除算ではSmith型の尺度調整で中間桁あふれを抑えます。

TIME
O(1)
SPACE
O(1)

上限: 実部・虚部と結果は有限数、0+0iによる除算は禁止

組合せ

覆面算

列ごとの繰上りを使う有界な指数時間バックトラッキングで、英大文字の加算覆面算を列挙します。

TIME
最悪O(10!·w)（指数時間）
SPACE
O(w+l+s)

上限: 加数2〜8語、各1〜12文字、異なる文字10種以下、解1〜100件、探索状態1〜2,000,000（既定1,000,000）

特殊関数

プサイ関数・ポリガンマ関数

漸近展開と最大100,000項の正級数・積分尾部補正でプサイ関数と0〜8階ポリガンマを評価する有界な倍精度近似です。

TIME
O(k)
SPACE
O(1)

上限: digammaは10⁻¹²≤x≤10⁶、polygammaは10⁻⁶≤x≤10⁶かつ階数0〜8。内部相対打切り基準10⁻¹⁶

計算機基礎

浮動小数点数

IEEE 754倍精度のビット表現を1だけ増減して隣接値、上下ULP、相対ULP、機械イプシロンを調べます。

TIME
O(1)
SPACE
O(1)

上限: 有限の倍精度数

圧縮

フラクタルによる画像圧縮

8種の幾何変換と収縮する輝度アフィン近似を総当たりし反復復元します。極小グレースケール画像だけの教育用で、実用・本番用コーデックではありません。

TIME
O(RD·8b² + ip)
SPACE
O(p+R)

上限: 4×4〜16×16、画素0〜255、ブロック辺2または4、domain最大64、復元1〜100回（既定24）、許容誤差10⁻¹²〜10（既定10⁻³）

フラクタル

フラクタル補間

節点を結ぶ収縮アフィンIFSを有限回展開し、点列・写像・収束推定と停止理由を返す安全な教育用近似です。

TIME
O(mp)
SPACE
O(p+m)

上限: 節点2〜16、座標−10⁹〜10⁹、収縮率−0.99〜0.99、1〜12反復（既定8）、2〜10,000点、許容誤差10⁻¹²〜1

基礎操作

ブロック移動

連続部分列を取り出して指定位置へ挿入し、旧添字から新添字への対応、逆操作、復元検証を返します。

TIME
O(n)
SPACE
O(n)

上限: 配列10,000要素以下、開始・個数・移動先は有効な整数添字

組合せ

分割数

一次元BigInt動的計画法で整数の分割数を厳密計算し、必要なら先頭から最大100件を非増加順に列挙します。

TIME
O(n²+Ln)
SPACE
O(n+Ln)

上限: 0≤n≤1,000、列挙上限0〜100、履歴256件

アルゴリズム設計

分割統治

数列を再帰的に二分し、左・右・中央をまたぐ候補を比較して最大和の連続部分配列と有界な再帰履歴を返します。

TIME
O(n log n)
SPACE
O(n)

上限: 有限数1〜10,000要素、深さ上限1〜64（既定32）、履歴256件

ソート

分布数えソート

値を数えて累積位置を作り、入力を後ろから配置することで整数列を安定に整列します。

TIME
O(n+r)
SPACE
O(n+r)

上限: 整数10,000要素以下、各値−1,000,000〜1,000,000、値域100,000以下、配置履歴256件

確率・統計

平均値・標準偏差

Welfordの一回走査で平均・分散・標準偏差を計算し、母集団または不偏標本分散を選べます。

TIME
O(n)
SPACE
O(n)

上限: 有限数100,000個以下。母集団は1個以上、標本は2個以上で累積値と結果が有限

数値解析

平方根

2進指数から初期値を選ぶNewton反復で非負数の平方根を求め、近似履歴・収束状態・停止理由を返します。

TIME
O(i)
SPACE
O(i)

上限: 0〜Number.MAX_VALUE、許容誤差10⁻¹⁵〜1、1〜1,000反復（既定10⁻¹²・100回）

特殊関数

ベータ関数

9個のLanczos定数による対数ガンマの差を指数化してベータ関数を求める、有界な倍精度近似です。

TIME
O(1)
SPACE
O(1)

上限: 10⁻¹²≤a,b≤10⁵、倍精度の有限結果を要求

確率・統計

ベータ分布

対数ガンマで密度を計算し、正則化不完全ベータ関数の有界な倍精度近似で累積確率と収束状態を返します。

TIME
O(i)
SPACE
O(1)

上限: 0≤x≤1、10⁻¹²≤α,β≤10⁵。密度が発散する境界は拒否、内部許容誤差10⁻¹⁴

線形代数

ベクトル

同次元の有限実ベクトルについて加算・減算・内積を行い、単一ベクトルのEuclidノルムも計算します。

TIME
O(n)
SPACE
O(n)

上限: 各ベクトル1〜10,000要素、二項演算は同次元、すべての結果は有限

数値解析

補間

重複しない節点からLagrange基底またはNewton差商で補間多項式を評価し、Newton法では係数も返します。

TIME
O(n²)
SPACE
O(n)

上限: 有限数のx・yを各1〜256個、同数でxは重複なし、評価点と全中間結果は有限

探索

補間探索

昇順数列の端値から探索位置を補間し、重複時は最初の一致まで左側を探索して各区間遷移を返します。

TIME
平均O(log log n)、最悪O(n)
SPACE
O(n)

上限: 昇順の有限数10,000要素以下、補間添字を安全整数として計算できること

最適化

ポリトープ法

2次元のsphere・Rosenbrock・Himmelblau関数を反射・展開・収縮・縮小で探索する微分不要のヒューリスティックで、大域最適の保証はありません。

TIME
O(i)
SPACE
O(i)

上限: 開始座標−10⁶〜10⁶、初期幅10⁻¹²〜10⁶、許容誤差10⁻¹⁵〜1、1〜1,000反復、目的関数評価3〜50,000回（既定10,000回）

ソート

マージ

比較関数で昇順と確認した2配列を二本のカーソルで安定に併合し、選択元の有界な遷移を返します。

TIME
O(n+m)
SPACE
O(n+m)

上限: 各配列および合計は10,000要素以下、比較関数は有限値を返すこと、履歴256件

ソート

マージソート

幅1から倍増する反復的なボトムアップ併合で、比較関数に対して安定に整列し、各パスと有界な併合履歴を返します。

TIME
O(n log n)
SPACE
O(n)

上限: 10,000要素以下、比較関数は有限値を返すこと、パス32件・併合履歴256件

組合せ

魔方陣

Siamese法で1からn²を配置し、行・列・対角線の和と魔法定数を検算します。奇数次数だけをサポートします。

TIME
O(n²)
SPACE
O(n²)

上限: 1〜15の奇数次数のみ。偶数次数は未対応

確率・統計

幹葉表示

有限数をscale倍して丸め、10で分けた幹ごとに葉を昇順で並べた幹葉表示を生成します。

TIME
O(n log n)
SPACE
O(n)

上限: 有限数1〜10,000個、10⁻⁶≤scale≤10⁶、値×scaleは安全整数

グラフ

水をはかる問題

2容器の注水・排水・移し替え状態を幅優先探索し、目標量への最短操作列を返します。

TIME
O(ab)
SPACE
O(ab)

上限: 容量は各1〜1,000の整数、目標は0〜大きい方の容量

確率・統計

無作為抽出

seed付きMulberry32と部分Fisher–Yates法または独立抽出で標本を返します。決定的な統計用疑似乱数であり、暗号学的に安全ではありません。

TIME
O(N+k)
SPACE
O(N+k+h)

上限: 母集団10,000要素以下、抽出10,000件以下、seedは0〜2³²−1、履歴10,000件以下

グラフ

迷路

seed付きxorshiftで再帰バックトラッカ型の完全迷路を生成し、幅優先探索で入口から出口への経路を求めます。

TIME
O(wh)
SPACE
O(wh)

上限: 幅・高さは3〜51の奇数、seedは0〜2³²−1、生成・探索履歴は各256件

計算幾何

面積

有限座標の多角形を靴紐公式で計算し、符号付き面積・絶対面積・頂点の向きを返します。

TIME
O(n)
SPACE
O(n)

上限: 有限座標の頂点3〜10,000個、面積計算結果は有限

探索

文字列照合

Unicode符号位置列を各開始位置から素朴に比較し、空パターンを含む全一致位置と比較履歴を返します。

TIME
O(nm)
SPACE
O(n+h)

上限: 本文・パターンは各10,000 Unicode符号位置以下、履歴256件

確率・統計

モンテカルロ法

seed付きMulberry32で[0,1]上の四分円またはx²の積分を標本平均・標準誤差付きで推定します。決定的な統計用疑似乱数であり、暗号学的に安全ではありません。

TIME
O(s)
SPACE
O(c)

上限: 標本1〜1,000,000、seedは0〜2³²−1、チェックポイント0〜1,000件

数論

有限体

素数pを試し割りで検証して素体GF(p)を構成し、加減乗除・累乗・逆元を剰余演算で厳密に行います。

TIME
構築O(√p)、累乗・逆元O(log e)
SPACE
O(1)

上限: pは2〜10,000,019の素数、元と指数は安全整数、指数は非負、0の逆元は禁止

データ構造

優先待ち行列

比較関数を用いる二分ヒープへpush・pop・peekを順に適用し、結果と有界な比較・交換履歴を返します。

TIME
O(m log m + S)
SPACE
O(m+S)

上限: 操作1,000件以下、履歴256件、スナップショット総要素20,000以下、比較結果は有限

数値解析

床・天井

有限の倍精度値について床・天井・0方向への丸め・床からの小数部分・整数判定を返します。

TIME
O(1)
SPACE
O(1)

上限: −Number.MAX_SAFE_INTEGER〜Number.MAX_SAFE_INTEGERの有限数

暦計算

曜日

先発グレゴリオ暦の日付を検証し、Zeller型の合同式で曜日名・日曜始まり添字・ISO曜日を返します。

TIME
O(1)
SPACE
O(1)

上限: 西暦1〜9999年の実在する月日

特殊関数

余弦積分

x≤16では級数、大きなxでは漸近展開を使い、余弦積分Ci(x)を停止理由・誤差指標付きで求める有界な倍精度近似です。

TIME
O(i)
SPACE
O(1)

上限: 10⁻¹²≤x≤10⁶、許容誤差10⁻¹⁶〜10⁻²、反復1〜10,000回（既定500回）

グラフ

横形探索

検証済み隣接リストをキューで幅優先探索し、訪問順・親・指定頂点への最短辺数経路を返します。

TIME
O(V+E)
SPACE
O(V+E)

上限: 頂点1〜512、辺4,096本以下、履歴256件

ソート

ラディックス・ソート

安全整数を符号で分け、10進LSDバケットを安定に通して負数を絶対値の逆順にまとめ、昇順列と各パスを返します。

TIME
O(dn+u log u)
SPACE
O(dn)

上限: 安全整数1,000要素以下

乱数

乱数

32ビットseedからMulberry32で[0,1)の再現可能な列と有界な状態履歴を生成します。決定的な統計用疑似乱数であり、暗号学的に安全ではありません。

TIME
O(k)
SPACE
O(k+h)

上限: seedは0〜2³²−1、生成100,000個以下、状態履歴10,000件以下

乱数

乱数の改良法

seed付きMulberry32から作るBernoulliビットを対で読み、Von Neumann法で同値対を捨てて出力します。出力も決定的で暗号学的に安全ではありません。

TIME
O(P)
SPACE
O(k+h)

上限: 0≤入力確率≤1、出力100,000ビット以下、最大1,000,000対、seedは0〜2³²−1、履歴10,000件以下

乱数

ランダムな順列

seed付きMulberry32によるFisher–Yates法で配列と元添字を並べ替えます。決定的な統計用疑似乱数であり、暗号学的に安全ではありません。

TIME
O(n)
SPACE
O(n+h)

上限: 配列100,000要素以下、seedは0〜2³²−1、交換履歴10,000件以下

データ構造

リスト

配列リストへ添字付きinsert・delete・get・setを順に適用し、結果と有界なスナップショットを返します。

TIME
O(mn+S)
SPACE
O(n+S)

上限: 初期要素・操作は各1,000件以下、結果リスト1,000要素以下、履歴256件・総要素20,000以下

数値解析

立方根

符号と2進指数から初期値を選ぶNewton反復で実立方根を求め、全近似履歴と停止理由を返します。

TIME
O(i)
SPACE
O(i)

上限: 入力は有限数、許容誤差10⁻¹⁵〜1、反復1〜1,000回（既定100回）

数値解析

累乗

安全整数指数は二乗反復、実数指数は定義域を検証したMath.powで計算し、有限結果と整数指数の履歴を返します。

TIME
整数指数O(log |e|)、実数指数O(1)
SPACE
整数指数O(log |e|)、実数指数O(1)

上限: 底・指数は有限、整数指数は安全整数、0の負冪と負の底の非整数実数冪は禁止、結果は有限

確率・統計

累乗分布

下限以上の正規化された累乗分布の密度・累積確率・分位点とseed付き逆変換標本を計算します。標本PRNGは決定的で暗号学的に安全ではありません。

TIME
評価O(1)、標本O(k)
SPACE
評価O(1)、標本O(k)

上限: alpha>1、minimum>0、xは有限、0≤p<1、標本100,000個以下、seedは0〜2³²−1、結果は有限

線形代数

累乗法

実正方行列へ正規化したべき乗反復を適用し、支配固有値・固有ベクトル・残差・全履歴と停止理由を返します。

TIME
O(i n²)
SPACE
O(n²+i)

上限: 有限数の1×1〜64×64行列、初期ベクトルは非零、許容誤差10⁻¹⁵〜1、反復1〜10,000回

圧縮

連長圧縮

Unicode符号位置の連続runを値と個数へ可逆符号化し、厳密なサイズメタデータ検証付きで上限内に展開します。

TIME
O(n)
SPACE
O(n)

上限: 入力・run数は10,000以下、展開上限0〜20,000符号位置、サイズメタデータにも個別上限あり

数値解析

連分数

有限係数の有限連分数を後ろから評価し、または1,000桁以内の有理数をEuclid互除法で単純連分数へ厳密展開・検算します。

TIME
O(k)
SPACE
O(k)

上限: 評価係数1〜1,000個、有理数の分子・分母は各1,000桁以内、展開1〜1,000項、分母0は禁止

数値解析

連分数補間

重複しない節点をすべて通るThiele型有限連分数係数を構成し、節点誤差の検証と任意点評価を返します。

TIME
O(n²)
SPACE
O(n)

上限: 有限数のx・yを各1〜64個、同数でxは重複なし、係数・評価結果は有限

線形代数

連立１次方程式

部分ピボット付きGauss消去と後退代入で実連立一次方程式を解き、ピボット・残差・残差ノルムを返します。

TIME
O(n³)
SPACE
O(n²)

上限: 有限数の1×1〜64×64正方行列と同長右辺、数値的に非特異で全中間結果が有限

確率・統計

ロジスティック分布

位置・尺度母数から数値安定なロジスティック密度・累積確率を求め、開区間確率の分位点も計算します。

TIME
O(1)
SPACE
O(1)

上限: x・locationは有限、scale>0、分位点は0<p<1で結果が有限

再帰

Ackermann関数

明示スタックでAckermann関数を評価し、必ず呼出回数・スタック深さ・出力値の厳格な上限で停止して理由を返します。

TIME
O(c)
SPACE
O(s)

上限: 0≤m≤4、0≤n≤100,000、呼出1〜1,000,000回、スタック1〜100,000、出力0〜Number.MAX_SAFE_INTEGER（各既定100,000回・10,000・10⁹）

数値解析

AitkenのΔ²法

連続する3項からAitkenのΔ²値を計算し、小さすぎる分母をguardして任意の真値に対する誤差も返します。

TIME
O(n)
SPACE
O(n)

上限: 有限数3〜10,000項、真値を指定する場合も有限

データ構造

B木

最小次数付きB木への重複なし挿入と探索を行い、分割・昇格・不変条件を検証する有界な教育用実装です。削除は未対応です。

TIME
O(m log n+S)
SPACE
O(n+S)

上限: insert/search操作・鍵は各512以下、最小次数2〜8、安全整数鍵、履歴256件・スナップショット総ノード20,000以下。削除非対応

数論

Bernoulli数

Akiyama–Tanigawa型の三角更新をBigInt有理数で行い、B₁=−1/2規約のBernoulli数を厳密に返します。

TIME
O(n²)
SPACE
O(n)

上限: 最大添字0〜200

特殊関数

Bessel関数

整数次数の第一種Bessel関数Jを|x|≤30では級数、それ以外では一次補正漸近式で求める有界な倍精度近似です。

TIME
O(n+i)
SPACE
O(1)

上限: 整数次数−50〜50、−10⁴≤x≤10⁴、許容誤差10⁻¹⁶〜10⁻²、反復1〜10,000回

計算幾何

Bézier曲線

De Casteljau法でBézier曲線を等間隔標本化し、境界・端点・凸包内性を検証して任意tの全補間段階も返します。

TIME
O(sn²)
SPACE
O(s+n²)

上限: 有限座標の制御点2〜32個、標本2〜5,000点、selectedTは0〜1、選択段階点は最大528個

探索

Boyer-Moore法

Unicode符号位置列へBoyer–Moore–Horspoolの不一致移動表を適用し、全一致位置と比較・移動履歴を返します。

TIME
最悪O(nm)
SPACE
O(m+h)

上限: 本文・パターンは各10,000 Unicode符号位置以下、履歴256件

フラクタル

C曲線

線分を直角二等辺の2辺へ反復置換してLévy C曲線の点・線分・全長・境界を生成し、線分上限なら低い次数で打ち切ります。

TIME
O(2ⁿ)
SPACE
O(2ⁿ)

上限: 有限座標の始点・終点、次数0〜13、出力線分上限1〜8,192、点は最大8,193

確率・統計

Cauchy分布

位置・尺度母数からCauchy分布の密度・累積確率を求め、開区間確率の分位点も計算します。

TIME
O(1)
SPACE
O(1)

上限: x・locationは有限、scale>0、分位点は0<p<1で結果が有限

数論

Collatzの予想

正整数から偶数なら半分、奇数なら3n+1の軌道を上限付きで検査します。返すのは確認済みの有限軌道であり、予想の証明ではありません。

TIME
O(s)
SPACE
O(s)

上限: 開始値1〜Number.MAX_SAFE_INTEGER、最大0〜100,000ステップ、値上限1〜Number.MAX_SAFE_INTEGER

誤り検出

CRC

UTF-8バイト列へCRC-16/IBM・CRC-16/CCITT-FALSE・CRC-32/ISO-HDLCまたは検証済み16/32ビット設定を適用します。CRCは整合性の誤り検出であり暗号ではありません。

TIME
O(b)
SPACE
O(c)

上限: 入力10,000 Unicode符号位置以下、幅16または32、polynomial・init・xorOutは幅内の非負整数

数論

Eratosthenesのふるい

2から上限までの倍数を型付き配列で合成数として印付けし、範囲内の全素数と個数を返します。

TIME
O(N log log N)
SPACE
O(N)

上限: 整数上限0〜10,000,000

数論

Eulerの関数

安全な正整数を試し割りで素因数分解し、積公式からEulerのφ関数を計算して因数による復元も検証します。

TIME
O(√n)
SPACE
O(log n)

上限: 1〜Number.MAX_SAFE_INTEGERの整数

組合せ

Euler数

sec xの規約E₀=1、E₂=−1、E₄=5に従い、奇数番を0としてEuler数をBigIntで厳密計算し漸化式も検証します。

TIME
O(n²)
SPACE
O(n)

上限: 最大添字は整数0〜100

確率・統計

F分布

正の実数自由度を持つF分布の密度と、正則化不完全ベータ連分数による累積確率・分位点を倍精度で近似し、収束情報を返します。

TIME
CDFはO(i)、分位点はO(qi)
SPACE
O(1)

上限: 0≤x≤10³⁰⁰、各自由度10⁻⁶〜10⁶、CDF反復10,000回以下、分位点確率10⁻¹²〜1−10⁻¹²・探索1,000回以下

数値解析

FFT

複素数列へビット反転付きradix-2 Cooley–Tukey FFTまたは正規化した逆変換を適用し、各段階と演算数を返します。

TIME
O(n log n)
SPACE
O(n)

上限: 長さ1〜4,096の2の累乗、各実部・虚部は有限数

数列

Fibonacci数列

F₀=0、F₁=1からBigIntで指定個数のFibonacci数を厳密生成し、漸化式と出力文字数を検証します。

TIME
O(kd)
SPACE
O(kd)

上限: 項数0〜4,096、添字単独計算は0〜5,000、出力合計200,000文字以下

探索

Fibonacci探索

有限数の昇順配列をFibonacci分割で探索し、重複時のfirst・last・any規約、比較位置と状態を返します。

TIME
O(log n+r)
SPACE
O(log n)

上限: 昇順の有限数10,000要素以下、targetは有限数

ソート

Gaussの整列

全要素対を比較して順位を決め、同値なら元添字を先にする安定な全対順位ソートとして昇順列・順位・検証結果を返します。

TIME
O(n²)
SPACE
O(n)

上限: 有限数512要素以下（空配列可）

線形代数

Gauss法

部分ピボット付き前進消去と後退代入で実正方連立方程式を解き、上三角拡大行列・ピボット・残差を返す教育用実装です。

TIME
O(n³)
SPACE
O(n²)

上限: 有限要素の1×1〜24×24正方行列、右辺長は次数と一致、数値的特異行列は不可

線形代数

Gauss-Jordan法

部分ピボット付きGauss–Jordan消去で有限実行列の簡約行階段形、ピボット、階数と特異性を求める教育用実装です。

TIME
O(rc min(r,c))
SPACE
O(rc)

上限: 有限要素の1〜24行・1〜24列の行列

線形代数

Gauss-Seidel法

実正方連立方程式を逐次更新するGauss–Seidel反復で解き、残差停止・有界履歴・正定値判定を返す教育用実装です。

TIME
O(i n²)
SPACE
O(n²+h)

上限: 有限要素の1×1〜24×24行列、許容誤差10⁻¹⁵〜1、反復1〜10,000回、履歴256件

符号

Gray符号

最大64ビットの非負整数を反射Gray符号へ厳密変換・逆変換し、出力上限内なら巡回Gray符号列と隣接1ビット性も生成検証します。

TIME
変換O(b)、列生成O(2ᵇb)
SPACE
O(2ᵇb)

上限: 変換は1〜64ビット、列生成は0〜64ビットかつ4,096件以下

数列

Hammingの問題

2・3・5倍を指す3本のポインタで重複なく昇順のHamming数をBigIntで厳密生成し、状態を有界記録します。

TIME
O(kd)
SPACE
O(kd)

上限: 項数0〜4,096、出力合計200,000文字以下、状態履歴512件

フラクタル

Hilbert曲線

Hilbert添字を整数格子座標へ反復変換し、指定上限までの点・線分・境界と隣接性・一意性の検証を返します。

TIME
O(pn)
SPACE
O(p)

上限: 次数0〜15、出力点1〜10,000点（超過分は明示的に打切り）

数値解析

Horner法

降べき係数の多項式をHorner法で評価し、同時に導関数、最大256段階の状態と直接評価との差を返します。

TIME
O(n)
SPACE
O(min(n,h))

上限: 有限係数1〜4,096個、−10¹⁰⁰≤x≤10¹⁰⁰、全計算結果が有限

線形代数

Householder変換

Householder反射で行数が列数以上の実行列をQとRへ分解し、再構成誤差・直交誤差・階数を返す教育用実装です。

TIME
O(mn²)
SPACE
O(m²+mn)

上限: 有限要素の1〜24行・1〜24列、行数は列数以上

圧縮

Huffman法

Unicode符号位置の頻度から決定的な接頭辞木を構築して符号化し、木・符号・頻度を厳密検証して復号する学習用形式です。汎用・本番圧縮形式ではありません。

TIME
O(n+s² log s)
SPACE
O(n+s)

上限: 入力20,000 Unicode符号位置以下、異なる記号4,096種以下、符号200,000ビット以下

誤り検出

ISBN

空白とハイフンを除去し、ISBN-10またはISBN-13の重み付きチェックディジットを生成・検証して計算項を返します。

TIME
O(1)
SPACE
O(1)

上限: ISBN-10は9桁本体または10桁、ISBN-13は12桁本体または13桁

線形代数

Jacobi法

実対称行列の最大非対角要素をJacobi回転で消去し、固有値・直交固有ベクトル・誤差と有界履歴を返す教育用実装です。

TIME
O(i n²)
SPACE
O(n²+h)

上限: 有限要素の対称1×1〜16×16行列、許容誤差10⁻¹⁵〜1、反復1〜10,000回、履歴256件

組合せ

Josephusの問題

円環配列から指定歩数ごとに人物を除去し、生存者、全除去順と上限付き状態を返します。

TIME
O(n²)
SPACE
O(n²)

上限: 人数1〜20,000、歩数1〜Number.MAX_SAFE_INTEGER、開始位置0〜n−1、状態履歴512件

フラクタル

Julia集合

固定複素定数に対するJulia集合を有界なCPU格子上のescape-time反復で計算し、作業上限とプレビュー打切りを明示します。

TIME
O(whi)
SPACE
O(wh)

上限: 幅・高さ各1〜200、反復1〜2,000、総反復2,000,000以下、プレビュー10,000点以下

乱数

Knuthの乱数発生法

Knuthの55語減算型生成器でseedから再現可能な統計・学習用列を生成し、同ページでWichmann–Hill法と比較します。どちらも暗号用途には使えません。

TIME
O(k)
SPACE
O(k+55h)

上限: seedは0〜2,147,483,646、生成100,000個以下、状態履歴10,000件以下

探索

Knuth-Morris-Pratt法

Unicode符号位置列の接頭辞表を構築して本文中の全一致位置を線形探索し、比較回数と最大512件の状態を返します。

TIME
O(n+m)
SPACE
O(m+h)

上限: 本文・パターンは各20,000 Unicode符号位置以下、履歴512件

フラクタル

Koch曲線

線分を4本へ反復置換してKoch曲線の点・線分・境界を生成し、線分上限に応じて生成次数を明示的に下げます。

TIME
O(4ⁿ)
SPACE
O(4ⁿ)

上限: 有限座標の始点・終点、要求次数0〜10、出力線分1〜10,000本

数値解析

Lagrange補間

重複しない節点から正規化した重心重みでLagrange補間値を求め、基底項と全節点の再現誤差を返します。

TIME
O(n²)
SPACE
O(n²)

上限: 有限数の節点・値1〜128組、xは有限、節点xは重複不可

計算幾何

Lissajous図形

振幅・周波数・位相・周期からLissajous曲線を等間隔に標本化し、点列・実際の母数・境界と有限性を返します。

TIME
O(s)
SPACE
O(s)

上限: 標本2〜20,000点、振幅0超〜10⁶、周波数0超〜10,000、周期0超〜10,000、位相は有限

力学系

Lorenzアトラクタ

Lorenz方程式を4次Runge–Kutta法で固定刻み積分し、全計算とは独立に間引いた軌道、停止理由と最終状態を返します。

TIME
O(p)
SPACE
O(p)

上限: 点数1〜100,000、刻み0超〜0.1、履歴1〜10,000点、各正の母数1,000以下、発散上限10¹²以下

線形代数

LU分解

部分ピボット付き実正方行列をP・L・Uへ分解し、置換、ピボットとPLU再構成誤差を返す教育用実装です。

TIME
O(n³)
SPACE
O(n²)

上限: 有限要素の1×1〜24×24正方行列、数値的特異行列は不可

圧縮

LZ法

Unicode符号位置列をLZ78のprefix・next tokenへ可逆変換し、辞書参照・展開長を厳密検証する学習用形式です。汎用・本番圧縮形式ではありません。

TIME
最悪O(n²)
SPACE
O(n²)

上限: 入力・展開は20,000 Unicode符号位置以下、tokenは20,000件以下、履歴512件

乱数

M系列乱数

検証済みビット幅・非零seedのFibonacci LFSRから決定的なビット列を生成し、周期と最大長性を検査します。統計・学習用で暗号用途には使えません。

TIME
O(k)
SPACE
O(k)

上限: 幅2〜16ビット、seed・tap maskは幅内の非零整数、生成100,000ビット以下、状態履歴10,000件以下

フラクタル

Mandelbrot集合

Mandelbrot集合をz₀=0から有界なCPU格子上のescape-time反復で計算し、作業上限とプレビュー打切りを明示します。

TIME
O(whi)
SPACE
O(wh)

上限: 幅・高さ各1〜200、反復1〜2,000、総反復2,000,000以下、プレビュー10,000点以下

再帰

McCarthy関数

McCarthy 91関数の入れ子再帰を明示的なpending数で実行し、厳格な呼出・スタック・履歴上限と未完了時の停止理由を返します。

TIME
O(c)
SPACE
O(h)

上限: 入力整数−1,000,000〜1,000,000、呼出1〜100,000回、pending 0〜10,000、履歴0〜512件

数値解析

Neville補間

重複しない節点へNevilleの三角漸化表を適用して補間値を求め、対角近似と全節点の再現誤差を返します。

TIME
O(n³)
SPACE
O(n²)

上限: 有限数の節点・値1〜128組、xは有限、節点xは重複不可

数値解析

Newton法

固定式cubicまたはcos-minus-xとその導関数だけを選びNewton反復し、関数・導関数で共有する評価上限、履歴と停止理由を返します。

TIME
O(i)
SPACE
O(i)

上限: 式はcubic・cos-minus-x、−10¹⁰⁰≤初期値≤10¹⁰⁰、反復1〜1,000回、関数・導関数の合計評価1〜10,000回

数値解析

Newton補間

重複しない節点の差商表とNewton係数を作り、入れ子積で補間値を評価して全節点の再現誤差を返します。求根のNewton法とは別手法です。

TIME
O(n²)
SPACE
O(n²)

上限: 有限数の節点・値1〜128組、xは有限、節点xは重複不可

機械学習

線形回帰

切片を含む最小二乗法で線形回帰を行い、係数・予測値・残差・決定係数を返します。

TIME
O(sd²+d³)
SPACE
O(sd+d²)

上限: 有限数の標本2〜1,000、特徴量1〜16、正規方程式が数値的に特異でないこと

機械学習

ロジスティック回帰

シグモイド交差エントロピーを勾配降下法で最小化し、二値予測・確率・反復ごとの損失と停止理由を返します。

TIME
O(isd)
SPACE
O(d+h)

上限: 標本2〜1,000、特徴量1〜16、反復1〜10,000、i×s×(d+1)≤5,000,000、履歴256件、ラベル0/1

機械学習

k-means法

決定的な遠点選択で初期中心を作り、割当と中心更新を反復してクラスタ・慣性・収束状態を返します。

TIME
O(isdk)
SPACE
O(sk+hk)

上限: 標本1〜1,000、特徴量1〜16、kは1〜16かつ標本数以下、反復1〜10,000、i×s×d×k≤5,000,000

機械学習

k近傍法

ユークリッド距離で近いk件を安定に選び、多数決と距離・元順によるタイブレークで分類します。距離が数値として表現できない入力は明示的に拒否します。

TIME
O(sd)
SPACE
O(s)

上限: 有限数の学習標本1〜1,000、特徴量1〜16、1≤k≤s、全距離が有限値で表現可能

機械学習

ナイーブベイズ

クラスごとのガウス分布を仮定して事前確率と特徴量尤度を計算し、クラス別確率と予測を返します。

TIME
O((s+q)dc)
SPACE
O(dc+q c)

上限: 学習標本2〜1,000、問合せ1〜1,000、特徴量1〜16、クラス1〜32、文字列ラベル100文字以下

機械学習

決定木

Gini不純度が最も下がる数値特徴量の分割を決定的に選び、深さ・ノード数を制限した分類木を構築します。

TIME
O(Dds log s)
SPACE
O(ds+n)

上限: 有限数の標本2〜256、特徴量1〜16、深さ0〜12、ノード1〜511、文字列ラベル100文字以下

機械学習

PCA（機械学習）

データを中心化して共分散行列をJacobi回転で固有分解し、主成分・寄与率・変換後データを返します。

TIME
O(id²)
SPACE
O(sd+d²)

上限: 有限数の標本2〜1,000、特徴量1〜16、成分1〜d、反復1〜10,000

機械学習

パーセプトロン

切片付き線形分類器をエポック単位で更新し、正解率・更新数・収束または上限到達を返します。

TIME
O(esd)
SPACE
O(d+h)

上限: 標本2〜1,000、特徴量1〜16、エポック1〜10,000、e×s×(d+1)≤5,000,000、ラベル0/1