What is algorithm?

「問題の解法で有限時間内に解が得られるもの」

My Definition

問題を解くための方法、その中で答えが出るもの

• 問題を解くための方法→手続き(procedure)
• 手続きの中で答えが出るもの→アルゴリズム

Problems

WHY are algorithms important?

• データ構造を知る
• サイトの高速化
• データに価値を見出す

data structure

• 配列
• リスト
• キュー
• スタック
• ツリー
• ハッシュ

Quick or Bubble?

条件: データ数 n

どちらが早いか?

Data mining

大規模データから特徴を抽出→カテゴライズ

マーケティングやコンテンツに

Major Algorithms

• ソート(sort)
• 探索(search)

Quick or Bubble?

バブルソート平均 O(n^2)

クイックソート平均 O(n log n)

平均ではクイックソートの方が早い!

  1 class Bubble
  2   def sort(data)
  3     for i in 0...data.length-1
  4       for j in 0...data.length-1-i
  5         data[j+1],data[j] = data[j],data[j+1] if data[j] > data[j+1]
  6       end
  7     end
  8     return data
  9   end
 10 end
						

  1 class Quick
  2   def left(piv, data)
  3     data.select{ |i| i < piv}
  4   end
  5   def right(piv, data)
  6     data.select{ |i| i >= piv}
  7   end
  8 
  9   def sort(data)
 10     return data if data.length.zero?
 11     piv = data.shift
 12     sort(left(piv,data)) + [piv] + sort(right(piv,data))
 13   end
 14 end
						

linear or binary?

線形探索平均 O(n)

2分探索平均 O(log n)

平均では2分探索の方が早い!ただし整列されている必要がある。