概要

アルゴリズム#アルゴリズム#

限られた時間内に特定の問題を解決する段階的なステップ

データ構造

データの組織とアクセスのシステム化方法

プログラム

アルゴリズム+データ構造

ぎじふごう

アルゴリズムを記述する高度な言語
自然言語の文よりも構造的で、プログラミング言語よりも詳細ではありません.

Alg arrayMax(Arr, n)
  input array Arr of n integers
  output maximun element of Arr
1. currenMax ← A[0]
2. for i ← 1 to n-1
     if(A[i] > currentMax)
       currentMax ← A[i]
3. return currentMax

コントロール

<if문>
if(exp)
  statement
elseif(exp)
  statement
else
  statement

<for문>
for var ← exp to exp
  statement
for var ← exp downto exp
  statement

<foreach문>
for each var ∈ exp
  statement

<while문>
while(exp)
  statement

<do-while문>
do
  statement
while(exp)

方法

Alg methodname(arg)	정의
  something
return exp			반환

methodname(arg)		호출

コメント

{ 주석내용 }

えんざん

←			치환
= < ≤ > ≥	관계 연산자
& || !		논리 연산자
s₁ n² 		수학적 표현 (쳠자 등)

ランダムアクセスマシンモデル

1つのCPU は、

個の無制限メモリユニットを有する

メモリユニットは、任意の数/文字データ

を格納順番にリストされる.

ランダムアクセスマシンがユニットにアクセスするのに常に一定の時間がかかる
3-1. ランダムアクセスマシンは、元のタスクを実行するとき、常に

の一定時間を維持する.

元のタスク

アルゴリズムが実行する基本計算は、偽コードとして表すことができる.
(e.g.) EXP, ASS, IND, CAL, RET

元のタスク数

アルゴリズムが実行する元のタスクの最大数は、コードを調べて、入力サイズの関数として決定できます.

Alg something(n)
  input integer n
  output integer m
  
1. m←0				{ASS / 1} 
2. for i←0 to n-1	{ASS, EXP / 2+n}
     m←i			{ASS / n}
3. return m			{RET / 1}
					{원시작업 갯수 합 : 1 + 2+n + n + 1 = 2n+3}

じっこうじかん

特長

実行時間は入力サイズとともに

増加する.

運転時間の最悪の分析は平均運転時間より分析しやすいが、最も重要なのは

である.

実験的方法で運転時間を推定する

コース

アルゴリズムを実装するプログラム

を記述する.

運転+システムコール測定運転時間

結果(e.g.:X軸入力サイズ/Y軸運転時間)を

グラフ形式で生成する.

制限

すべての入力の結果を反映できない

複数のアルゴリズムを比較するには、同じハードウェア、ソフトウェア環境

が必要である.

アルゴリズムを完全なプログラムとして

を実施することは困難である.

理論的方法で実行時間を推定する

特徴←実験的方法の限界を解決する

全ての入力可能性を考慮する

.

hw,sw武官

の疑似コード表現を使用するアルゴリズム

運転時間推定

世帯원시작업 수 : 5n+3 T(n) : 알고리즘 T에 대한 최악의 실행시간 a : 가장 빠른 원시작업의 실행 시간 b : 가장 느린 원시작업의 실행 시간

運転時間T(n)
a(5n+3) ≤ T(n) ≤ b(5n+3)

稼働時間の増加率

実行時間の増加率は、いくつかのアルゴリズムの固有の属性です.
リストされた順序で、入力サイズによって実行時間の増加率が大きい
関数形式関数名n=100の場合、値c定数関数1 lognログ関数7 log 2 nログ二乗関数49 n線形関数102 nlognログ線形関数7*102 n 22次関数104 n 33次関数1062 n指数関数1030

Big-Oh記号

与えられた2つの関数f(n)とg(n)について.
すべての整数n≧n 0に対してf(n)≦c・g(n)が成立する場合
実数の定数c>0と整数の定数n 0≧1が存在する場合、
「f(n)=O(g(n)」を表す.
関数成長率の上限を表します.f(n) = O(g(n))→f(n)の成長率はg(n)の成長率を超えない.
→漸近f(n)≦g(n).
(e.g.)
f(n) = 7n-2
-->f(n)=O(n).
-->7 n-2≦cn c=7、n 0=1に満足

Big-Omega記号

与えられた2つの関数f(n)とg(n)について.
すべての整数n≧n 0に対してf(n)≧c・g(n)が成立する場合
実数の定数c>0と整数の定数n 0≧1が存在する場合、
「f(n)=Ω(g(n))」と呼ぶ.
関数成長率の下限を表します.f(n) = Ω(g(n))→f(n)の成長率はg(n)の成長率を上回る.
→漸近f(n)≧g(n).

Big-thetaマーキング

与えられた2つの関数f(n)とg(n)について.
すべての整数n≧n 0に対して、c′・g(n)≦f(n)≦c′・g(n)が成立する
実数の定数c'>0が存在する場合、c'>0および整数の定数n 0≧1である.
"f(n)=Θ(g(n))”.
関数の成長率の上下限を表します.(=同じ関数を表します.)f(n) = Θ(g(n))→ f(n) = O(g(n)) = Ω(g(n))
→漸近はf(n)=g(n)である.