計算量(時間計算量)

情報処理用語集

計算量(時間計算量)

情報処理関連の用語について、基本的知識を紹介しているサイトです。近年、情報処理はインターネットなどの普及により、毎日生活していく中で熟知され、さまざまなシーンで利用されており日常生活の一部になりつつあります。コンピュータ社会において、技術の急激な進歩や発展に伴い情報処理用語も大幅に増えてきております。膨大な量の用語を全てご紹介するのは難儀ではありますが、多様化する現状に対応して、基本的な用語から、コンピュータ全般、ソフトウェア、アルゴリズムとデータ構造、システム開発の基礎、ファイルとデータベース、通信ネットワーク、情報処理システム、産業社会と情報化、情報化の課題など、いろいろな観点から用語を努めて簡潔で、できる限り解りやすく、丁寧に説明させていただいております。情報処理関連用語の理解やスキルアップで多くの情報と知識を習得していただけたら幸いです。「初級上級システムアドミニストレータ」や「上級システムアドミニストレータ」、「基本情報技術者」、「特種情報処理技術者」、「ソフトウェア開発技術者」などIT技術関連の試験対策にも是非、お役立てください。情報処理用語集は情報処理技術者試験資格取得を目指すあなたを応援させていただきます。

計算量(時間計算量)


スポンサードリンク






情報処理用語集
TOP


A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z 数字



スポンサードリンク







情報処理用語集>計算量(時間計算量)

computational complexity


計算量時間計算量)とは、コンピュータが規定の手順に従って

与えられた問題を解く際の指標である。


与えられた問題を解くときに結果を得るまでに必要な計算回数や時間など、

アルゴリズムを評価するために用いられる。

計算複雑度計算の手間などともいう。


例えば、『2×3』のかけ算を、足し算で表す場合『2+2+2』でも、

『3+3』でも手間に大きな差はないが、「1000×3」の場合、

「1000+1000+1000」のように1000を3回加えるのと

「3+3+3+・・・・+3」のように3を1000回加えるのでは、

手間に大きな差が出る。

そこで、アルゴリズムを思考ときは、なるべく手間が少なくなるようにする。


ただし、計算時間と必要な記憶領域は、一方を優先すればもう一方が

悪化するというトレードオフの関係にあることが多い。

T計算時間は遅いが記憶容量が少なくてすむアルゴリズム

U計算時間は早いが記憶容量を大量に必要とするアルゴリズム

T、Uのどちらのアルゴリズムを採用するかを決断する能力が必要とされる。


@時間計算量(time complexity):実行される命令、計算に要する時間

A領域計算量(space complexity):計算に必要な記憶領域の大きさ

単に計算量といった場合は時間計算量を指し、計算量が最大となる

最悪の場合を最大計算量(worst−case complexity)といい、

平均的な計算量を平均計算量(acerage complexity)という。


計算量は、(オーダー)という記号で表し、データ数nに対して、

計算量が比例して大きくなる場合には(n)と表す。




スポンサードリンク


Copyright (C) 情報処理用語集 All Rights Reserved