数理科学IIA（第5回）

今回は、計算量の表記法について説明した後、1変数多項式の四則演算の計算量解析について説明しました。

今回、計算量の基本とした演算は、係数どうしの加減乗除で、これを伴わないような単項や多項式の和は除きました。この辺は、計算機における多項式の内部表現と合わせて議論する必要があると思いますが、ひとまず単純な解析をしています。なお、擬剰余の計算量解析をレポート課題にしました。

次回からは1変数多項式に対する拡張 Euclid の互除法を扱う予定です。