# 問題解決力を鍛える！アルゴリズムとデータ構造
## 第2章
- 任意参加
- ファシリテーター: 辻田
### 話す・書く順番決めルーレット
in Ruby
```ruby
['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita'].shuffle.each { |v| puts ">[name=#{v}]\n\n" }
```
in JavaScript
```javascript
const l = ['hsu', 'chen', 'teruya', 'kanazawa', 'okura', 'tsujita']
l[Math.floor(Math.random()*l.length)]
```
### ファシリテーター決め方
- `%w(hsu chen teruya kanazawa okura kanno)`の順番でやっていく
### 参加者がやること
- 事前に決められた章を読む
- 学んだことやわからなかったことを書き込む（任意）
当日
- 最初に感想や質問を書く時間を設ける(10分)
- 時間枠 60分
- 延長枠 30分
### 勉強会時にやること
各自学びや気付き、疑問を発表していく
ファシリテーターがよしなに議論を進める
終了前に勉強会を振り返る？（KPTなどで）← 60分のときに仮締め
## 各自が書き込む場所
>[name=okura]
### 2.1 計算量とは
「計算量」という単語は逐語訳すると「計算複雑性」となり、こちらのほうがわかりやすくなるような気がする。
### 2.2 計算量のオーダー記法
Nが大きくなるなら極限っぽい考え方ができるよね、というのがポイントなのかな。
### 2.3 計算量を求める例(1)：偶数の列挙
~~CRubyの`even?`メソッド の実装を見てみても面白いかもしれない。
### 2.4 計算量を求める例(2)：最近点対問題
分割統治法、興味ある。
### 2.5 計算量の使い方
Nの大きさが重要。Webの世界だと実はNってそんなに大きくならないのかも（ユーザーが100万人いても、100万という数はこの世界ではそこまで大きくはない）。
### 2.6 計算量に関する注釈
最悪のケースを考えるのは大事だけど、Webの場合は時間に対する厳しさがそこまでではない（レスポンスに10秒とかかかっても問題ないときもある）から平均の方が重要だと思う。
### 2.7 ランダウのO記法の詳細
ΩとΘは知らなかった。
### 章末問題
2.6がよくわからなかった。
>[name=teruya]
2.1 計算量とは（年齢当てゲーム）
Rubyで書いてみました
```ruby=
def bsearch(nums, age, count)
count += 1
target_index = nums.size / 2
answer = nums[target_index]
puts "A: Are you #{answer} years old?(trial: #{count})"
if age == answer
puts "B: Yes, I am #{answer} years old!"
return
elsif age > answer
puts "B: No, I am older than #{answer} years old."
bsearch(nums[target_index + 1..], age, count)
else
puts "B: No, I am younger than #{answer} years old."
bsearch(nums[...target_index], age, count)
end
end
bsearch((0..65535).to_a, 25642, 0)
=>
A: Are you 32768 years old?(trial: 1)
B: No, I am younger than 32768 years old.
A: Are you 16384 years old?(trial: 2)
B: No, I am older than 16384 years old.
A: Are you 24576 years old?(trial: 3)
B: No, I am older than 24576 years old.
A: Are you 28672 years old?(trial: 4)
B: No, I am younger than 28672 years old.
A: Are you 26624 years old?(trial: 5)
B: No, I am younger than 26624 years old.
A: Are you 25600 years old?(trial: 6)
B: No, I am older than 25600 years old.
A: Are you 26112 years old?(trial: 7)
B: No, I am younger than 26112 years old.
A: Are you 25856 years old?(trial: 8)
B: No, I am younger than 25856 years old.
A: Are you 25728 years old?(trial: 9)
B: No, I am younger than 25728 years old.
A: Are you 25664 years old?(trial: 10)
B: No, I am younger than 25664 years old.
A: Are you 25632 years old?(trial: 11)
B: No, I am older than 25632 years old.
A: Are you 25648 years old?(trial: 12)
B: No, I am younger than 25648 years old.
A: Are you 25640 years old?(trial: 13)
B: No, I am older than 25640 years old.
A: Are you 25644 years old?(trial: 14)
B: No, I am younger than 25644 years old.
A: Are you 25642 years old?(trial: 15)
B: Yes, I am 25642 years old!
```
なおRubyには https://docs.ruby-lang.org/ja/latest/method/Array/i/bsearch.html があります、便利！
表2.1 Nの値の増加にともなう計算時間の増加具合
これはC++準拠の実行時間だと思うのですが、RubyではO(10^8)くらいから耐えられなくなります…。
```ruby=
def double_loop(loop)
count = 0
loop.times do
loop.times do
count += 1 # ここの処理の重さは重要ではない
end
end
puts count
end
double_loop(1000) # O(10^6)←一瞬で終わる
double_loop(10000) # O(10^8)←数秒かかる
double_loop(100000) # O(10^10)←たぶん10分くらいかかる
```
>[name=tsujita]
> 2.1
> そのような基準として特に重要なものが計算量という概念です
- インクリメントする時の処理が何回行われるか・・などに着目したことがなかった
- 実際にプログラミングしなくても見積もれるのは便利だけどその計算が難しかった
> 2.6 計算量に関する注釈
- 時間計算量と領域計算量（メモリ）、考え方の切り分け？をしたことがなかったので勉強になりました
プログラミングではベンチマークツール(?)を使っているイメージ
## 振り返り
>[name=okura]
次の章からはコードを書かないとわけがわからなくなりそう。
ところで、時間計算量と領域計算量はトレードオフかと思いきや、遅いソフトウェアはちゃっかりメモリも爆食いしていたりします。
https://github.com/okuramasafumi/alba/tree/main/benchmark
>[name=teruya]
領域計算量でつまずいたことがないのであまり考えたことがない…（最近のマシンは高スペックだからそうなりがちかも？）
アルゴリズムをいじって実際に測ってみると面白いです
https://gogutan.hatenablog.com/entry/2020/03/19/044546
>[name=tsujita]
アルゴリズム、新たな発見がたくさんあって面白いです
## 終了後ファシリテーターがやること
- 次回のファシリテーターを決める
- hsuさん
- 読む範囲を決める
- 第３章
Sign in with Wallet
Connect another wallet