基本情報技術者試験対策 その4

整列法

名称      :時間計算量   :特徴

選択ソート   :O(N^2)  :データの移動が少ない

バブルソート  :O(N^2)  :特に長所はない

挿入ソート   :O(N^2)  :ほとんど整列済みのとき高速

シェルソート  :O(N^1.25)  :高速かつロジックが簡単

マージソート  :O(N・logN):リスト向き、安定した速度

ヒープソート  :O(N・logN):安定した速度

クイックソート :O(N・logN):高速だが複雑な処理

 

探索法

名称    :計算量    :特徴

線形探索法 :O(N)  :先頭から順に探索。単純で力任せ

2分探索法 :O(logN):整列されたデータの中央調べて

             半分に絞り込むことを繰り返す

ハッシュ法 :O(1)   :ハッシュ関数で場所を計算。衝突の対処が必要

 

再起呼び出し

プログラムが自分自身を、直接または間接的に呼び出していること

 

高水準言語の分類

分類         :説明

手続き型言語     :プログラムを状態を変化させる命令文の列としてとらえる

オブジェクト指向言語 :データと操作を一体にしたオブジェクトを、

            プログラミングの中心とする

関数型言語      :コンピュータによる計算を、

            関数の組み合わせとしてとらえる

論理型言語      :公理(論理式)の集合を定義し、

            推理規則の適用により計算を行う

スクリプト言語    :比較的単純なプログラムを記述するための簡易的な言語

 

HTMLとXML

言語  :タグ         :目的

HTML  :決まったもののみ使用 :Webページ作成

XML  :自由に定義できる   :汎用的なデータ交換