時間複雑度+コア理論の定理

試験情報

実習

の4つの問題があります.実習時に解答する問題+新しい問題(1-2個)

リンクリスト

ごみ収集器:後で必要に応じて削除したデータを再呼び出すことができます.

1)位置がない場合=>find and insert,delete

単一リンクリスト

head:O(1)

に添付
削除

head:O(1)

tail:O(1)

に添付
削除

tail:O(n)=>tailのdelete演算は無効です!

tail前面の挿入/削除:O(n)=>前面の位置が見つからず、

を見つけるには長い時間がかかります.

の間に挿入する位置:O(n)

削除

の中央の位置:O(n)

ダブルリンクリスト

head:O(1)

に添付
削除

head:O(1)

tail:O(1)

に添付
削除

tail:O(1)

tail前挿入/削除:O(1)

の間に挿入する位置:O(n)

削除

の中央の位置:O(n)

2）位置決め時、=>直接挿入、削除

単一リンクリスト
挿入/削除:O(1)

p前挿入/削除:O(n)

ダブルリンクリスト
挿入/削除:O(1)

p前挿入/削除:O(1)

スタック

アレイに基づく

access point : int top = -1;

空間:O(N)

push,pop,top:O(1)=>すべての演算O(1)

t : 꼭대기 인덱스 번호

Algorithm push(o)
  if t = S.size()-1 then
    throw StackFull
  else
    t <- t+1
    S[t] = o

Algorithm pop()
  if empty() then
    throw StackEmpty
  else
    t <- t-1
    return S[t+1]

Algoritm top()
  if empty() then
    throw StackEmpty
  else
    return S[t]

Algorithm size()
  return t+1

Algorithm empty()
  if size() = 0 then
    return true
  else
    return false

単一リンクリストに基づく

access top : Node* top;

空間:O(n)

すべての演算O(1)

topノードをheadノードとします.(tailがtopの場合pop演算はO(n))

使用範囲:塩水湖上場運転時スタック、Webブラウザの後退ボタン、保存コマンドによりUndo機能

を実現する.

  
Algorithm push(data)
  p <- new node pointer struct(?)
  p.data <- data
  topNode.next <- p  // topNode : 꼭대기 노드형 포인터
  topNode <- p 
  size <- size + 1
  
Algorithm pop()
  p <- new pointer node
  p <- top
  top <- top.next
  delete p
  size <- size - 1
  
Algorithm top()
  if empty() then
    throw StackFull
  else
    return top.data;
    
Algorithm empty()
  if size() = 0 then
    return true
  else
    return false

Algorthm size()
  return size;

キュー

リングアレイベース

access point : front, rear

full :

空間:O(N)

すべての演算O(1)-enqueue、dequeue、front

使用範囲:共通部門キュー、共有プリンタ、マルチプログラミング

ポストインデックス変数:ポスト要素を表す次のインデックス

mod N:インデックス範囲を0～N-1に設定

Algorithm enqueue(o)
  if size() = N-1 then  // N:배열의크기(capacity)
    throw QueueFull
  else
    arr[rear] <- o
    rear = (rear+1) mod N
    n <- n + 1

Algorithm dequeue()
  if empty() then
    QueueEmpty
  else
    front = (front+1) mod N
    return arr[front-1]

Algorithm front()
  return arr[front]

Algorithm size()
  return n

Algorithm empty()
  if top = -1
    return true
  else
    return false

単一リンクリストに基づく

access point : Node frontNode, Node rearNode
※ループ配列とは異なり、開始要素、最後の要素(ループ配列が後方で最後)

を直接指す.

空間:O(n)

すべての演算O(1)

dequeueは前に行わなければならない(後に行われる場合の削除操作はO(n)

)

Algorithm enqueue(o)
  if size() = N-1 then
    throw QueueFull
  else
    tmp <- new node pointer 
    tmp.data = o
    rear.next = tmp
    rear <- tmp
    n <- n + 1

Algorithm dequeue()
  if empty() then
    throw QueueFull
  else
    tmp <- front
    front <- front.next
    n <- n + 1
    delete tmp

Algorithm front()
  if empty() then
    throw QueueFull
  else
    return front.data

ベクトル

ループアレイを使用して実装する場合、インデックスと実際のインデックスは異なる場合があります.

リングアレイで実装する場合は、insert(0,x)やerase(0)などの「O(1)」の前の挿入/削除のみが使用可能です.

空間:O(N)(N:初期割当て配列のサイズ)

insert

案:O(n)

リングアレイ:O(n)(前面挿入O(1)

)

Growable-Array

O(1)(未満時挿入)

O(1)(満タン時にinsert.doublingポリシーを採用)

O(n)(フルタイムinsert.インクリメンタルポリシーが実施されている場合)

erase

案:O(n)

リングアレイ:O(n)(前面の消去はO(1)

)

残りの演算子at(i)、set(i,o)、empty()およびsize()はいずれもO(1)である

Algorithm insert(o)   // 배열의 끝에 삽입 (=insert(n,o))
  if t = S.length - 1 then  // t : 배열의 끝 인덱스  S : 배열의 크기(capacity)
    A <- new array of 
      size...
    for i <- 0 to n-1 do
      A[i] <- S[i]
    S <- A
    n <- n+1

position

データ構造が内部でどのように実現されているかを考慮することなく、データ構造に必要な要素の場所に外部からアクセスできます.

p.element():O(1)=>位置決めpに返される値
(pが位置を表す変数、例えば反復器のbeginである場合)

positionは「位置」の概念ですが、カニは「ポインタ、すなわちアドレス(address)」です.
=>アドレスとして、アドレスのelementを返すという意味です!

インベントリ

access point : Node begin, Node end
※beginは開始要素、endは最後の要素の次のアドレスを指します.
begin = header
end = tailer → next

空間:O(n)の使用

リストの各位置はO(1)の空間(=オブジェクト位置;ポインタで位置を計算するときはポインタオブジェクト+アドレス値)を占有し、n個の要素がある場合はO(n)の空間

である.

全ての演算O(1)

size(), empty()

begin():リストの先頭アドレス(戻りヘッダ->next)

を返します.

end():リストの最後のアドレス「次のアドレス」を返します.

insert(p,e), erase(p)

insertFront(e), insertBack(e)

eraseFront(), eraseBack()

// p앞에다 데이터 e를 가지는 새로운 노드q를 삽입

Algorithm insert(p, e): {insert e before p} 
  Create a new node q
  q.data <- e
  q.prev <- p.prev
  q.next <- p
  q.prev.next <- q
  q.prev <- q
  n <- n + 1
  
Algorithm erase(p) 
  p.prev.next <- p.next
  p.next.prev <- p.prev
  delete p (또는 free p)
  n <- n-1

場所に基づいてデータ構造内のデータにアクセス

外部ではこれらのデータ構造をpositionと呼ぶが,内部はインデックス,ノードポインタである.等位置変換後アクセス可能

外部から反復器を使用してリストに必要なデータの場所を検索してアクセスできます(この場合、反復器は一番前と一番後ろの要素のみにアクセスします).

iteratorから開始し、特定の場所の5番目の場所を見つけた場合は、5番目の場所のアドレス値に変換して、ダブルリストを含む内部で操作できます.

シーケンス#シーケンス#

リングアレイ:insert(p,e),erase(p)O(n)を用いた.残りはすべてO(1)

二重リンクリスト:atindex(i)、indexOf(p)はO(n).残りはすべてO(1)

メソッドタイプ

1)リストベースのメソッド(=アクセス先のメソッド)

insertFront(o), insertBack(o), insert(p,o)

eraseFront(), eraseBack(), erase(p)

2)indexでアクセスする方法

atIndex(i), indexOf(p)

3)その他の方法

size(), empty()

シーケンスの詳細

リングアレイの使用

配列の各インデックスルームには、位置(=アドレス値)

が格納.

各位置のシーケンスオブジェクト構成:データフィールド+インデックスフィールド

データフィールドは、他のデータオブジェクトのポインタ変数アドレス値o

を記憶する.

insert(p,e) : O(n)

リングアレイに挿入すると、以前アレイに記憶されていた位置値を後押しする

.

各位置のシーケンスオブジェクトのインデックスフィールド値も1

増加する.

insertFront, eraseFront, insertBack, eraseBack : O(1)

insertFront:インデックスfの前のセルに位置を挿入し、fを1

減少する.

eraseFront:インデックスfの値を1

増加
=>insertFront、eraseFront演算は、fインクリメントの回数を毎回カウントして保存します.次に、後で夜中に計算した情報に基づいて、リング配列とシーケンスオブジェクトの不一致インデックス値を一致させるように並べ替えます.
(fと0番インデックスの違いを計算してソート)

atIndex(i) : O(1)

i:ループアレイ上のインデックスではなく、シーケンスオブジェクト上のインデックス

シーケンスのインデックスがリングアレイのインデックスとどれだけ一致しないか.
ex)i=3,f=1の場合、ループアレイ内のシーケンスオブジェクトのループアレイの位置は、ループアレイ内の3+1=4インデックスに格納されます=>ループアレイ内の4番目の部屋の位置に近づくことによって、シーケンスオブジェクトのデータ値が返されます.

indexOf(p) : O(1)

指定したアドレス値(場所)のシーケンス・オブジェクトを検索し、インデックス・フィールドの値を返すための実際のアドレス値を指定します.

二重リンクリストを使用して実装

atIndex(i):インデックスiの実際の場所に移動し、データにアクセスします.

反復器から始まり、for文(=O(n)に達した後、その部屋のシーケンスオブジェクトのデータ(=O(1)

)を問い合わせる.

indexOf(p):iterator pが指すオブジェクトからカウント回数を戻し、最前面に逆方向に到達するまで

挿入・消去ともに位置を使用するためO(1)