工学部計数工学科
計数工学とは?
計数とは
数理情報工学コース
システム情報工学コース
理念と歴史(数理情報工学)
理念と歴史(システム情報工学)
応用物理学部門とは
カリキュラム
履修ガイド
講義内容と時間割
学生実験(数理情報工学)
学生実験(システム情報工学)
企業見学・実地演習
輪講(数理情報工学)
輪講(システム情報工学)
学生生活
進学から卒業まで
就職・大学院進学状況
イベント紹介:五月祭工学博覧会
教員と研究室
教員と研究室一覧(数理情報工学)
教員と研究室一覧(システム情報工学)
研究活動
学位論文テーマ一覧(数理情報工学)
学位論文テーマ一覧(システム情報工学)
施設・設備
Technical Reports
大学院
数理情報学専攻
システム情報学専攻
大学院入学案内
関連研究科・専攻へのリンク
駒場生のみなさんへ
駒場での講義
学科パンフレット
駒場生進学ガイダンス
計数工学科への進学内定者の声
アクセス
お問い合わせ相談窓口
計測同窓会
English
計算複雑度
計算機の能力が向上することにより現実的な時間で解けるようになった問題は多いが,計算能力の向上だけでは対処できない問題も存在する.こうした問題では計算対象の大きさが少し増えるだけで計算の手間が大きく増大し,これはその問題が本質的に難しいことを意味している.この計算時間に関する問題の難しさを計る指標が計算複雑度である.計算対象の大きさを変数として,その大きさに対して線形(一次式),多項式,指数関数というように表現する.同様に,計算に必要とされる空間量の指標を空間複雑度という.