ヤマザキの地球偵察記録

ヤマザキさんの個人的な記録・備忘録です。

情報工学レクチャーシリーズ:アルゴリズムとデータ構造 第二章「アルゴリズムの基本データ構造」

配列

  • メモリ上に連続した領域を確保する
  • データの追加・削除は先頭から走査する必要があるので {O(n)}
  • 書き込み、読み込み共に {O(1)}
  • 配列は宣言時の長さから変更が出来ない = いわゆる静的配列

連結リスト

  • メモリ上に連続して領域を確保するわけではなく、必要に応じて確保する
  • {データ、次のレコードを指すポインタ}という構造の構造体と、リストの先頭を指すポインタから構成される
  • リスト先頭に対するデータの追加、削除は {O(1)}
  • 連結リスト内の要素の探索は時間がかかる
  • リストの構造上、使用するメモリ領域は配列よりも大きくなる

スタック

  • LIFO (Last In First Out)
  • 後から入れたものが先に出て行く構造
  • pushでデータの追加、popでデータの取り出しを行う
  • push, pop のどちらも {O(1)}

キュー

  • FIFO (First In First Out)
  • 先に入れた奴が先に出て行く構造
  • enqueueでデータの追加、dequeueでデータの取り出しを行う
  • enqueue, dequeueのどちらも {O(1)}

情報工学レクチャーシリーズ:アルゴリズムとデータ構造 第一章「アルゴリズムの基礎」

アルゴリズムとは

  • ある問題に対して、正しい解を得るための手順を定式化した形で表したもの

アルゴリズムの評価基準

  • 得られた解の質の良し悪し
  • 解を得るまでの計算時間・計算量

計算量の漸近的評価

  • 漸近的な時間計算量をオーダ記法を用いて表す
  • 漸近的な大小関係の参考:
\log{n} < n^{1/2} < n < n*\log{n} < n^{2} < n^{3} < ... < 2^{n} < n!

用語

  • 漸近的:徐々に近づくが、永遠の時間をかけても到達できない

「どうぞよろしく」と「どうかよろしく」

「どうぞ」と「どうか」の使い分けがよく分からなかったので、調べてみた。知恵袋などで質問が上がっていたのでそれを参照した。

「どうぞ」は丁寧な依頼

「どうか」は強い依頼

切羽詰って本当にお金を貸して欲しい時には、「どうぞお金を貸してください」ではなく、「どうかお金を貸してください」  

丁寧なあいさつ という意図であれば、「どうぞよろしくお願いします」

ぜひよろしく という意図であれば、「どうかよろしくお願いします」

ログファイルをリアルタイムで監視するコマンド

出力されたログをリアルタイムで追っていく際に使用できる。 tail コマンドにオプション f を追加するだけ。

tail -f [file name]

たまに less だったか more だったかなってなるから書いておく。