アルゴリズム論特論（塩田）　2017年度教材　第4回

  • 復習
    • 自然数 n のビット長は O(log n)
    • n 以下の２数の加法の計算量は O(log n)
    • n 以下の２数の減法の計算量は O(log n)
    • n 以下の２数の乗法の計算量は O(log2n)
    • a ÷ b の計算量は、商を q として O(log b× log q)
    • n 以下の２数の除法の計算量は大雑把に O(log2n)

  • 授業内容
    • ユークリッドのアルゴリズムの計算量

  • ツボ
    • ユークリッドのアルゴリズムの入力を a, b ( a > b > 0 ) とするとき、その計算量は O(log2a)

戻る