Hello there! 2 ヶ月以上コードを書かなかったり触らなかったりした後、ようやく戻ってきました。 私は結婚式の準備とプランニングに巻き込まれました。 ウェディングプランナーなしで海外挙式を成功させるのは難しいです。 でも、その甲斐あって、私たちの結婚式は最高のものになりました。
就職活動を始める前に、まず何を見直すか決めるのは大変でした。 プログラミングの核となるアルゴリズムとデータ構造という古典的なものから始めるべきだと思いました。 どんなシステムでも、データが大きくなっても、正しいアルゴリズムが使われていれば、性能は問題にならないはずです。
今日は、2種類のビッグオー記法、線形アルゴリズムと対数アルゴリズムについて簡単にブログを書きますね。
最初にビッグ O 表記について少し説明します。
漸近解析
漸近解析とは、数学的計算に基づいて、基本的に入力データセットが大きくなったときのアルゴリズムの効率を測定するものです (Wikipedia ありがとう！)。 適用する場所によって漸近分析の種類は異なりますが、コンピューター サイエンスでは、一般にビッグ O 記法としてフォーマットされます。
線形 vs. 対数
ビッグ O 記法を簡単に理解するために、これらの 2 つのアルゴリズムを比較します。
let numberList =
線形 O(n) – データが大きくなると性能が低下する。
線形または「ブルートフォース」手法では、性能は入力サイズに依存します。 この例では、配列の各項目を読み込んで、必要な数を検索します。 簡単だ！
//Logarithmic Time - O(n)func linear(key: Int) {
for (index, number) in numberList.enumerated() {
if number == key {
print("Value found in index \(index)")
break
}
}
}
もちろん、これは私たちの小さなデータセットには有効ですが、数千、数百万のデータがある場合は、あまり効率的ではありません。
Logarithmic O(log N) – 目標値を見つけるまでデータセットを繰り返し半分にすることで探索を絞り込む。
Using binary search – これは対数アルゴリズムの一形態で、配列内の中央値を見つけ、それを目標値と比較します。 アルゴリズムは、ターゲット値が中央値より高いか、低いか、または等しいかによって、上方または下方に移動します。
func binarySearch(key: Int, iminIndex: Int, imaxIndex: Int) {let midIndex = round(Double(iminIndex + imaxIndex)/2)
let midNumber = numberList
var result = ""//using recursion, we can go up or down the array and reduce the range
if midNumber > key { //target is less than the median so traverse downwards binarySearch(key: key, iminIndex: iminIndex, imaxIndex: Int(midIndex) - 1) } else if midNumber < key { //target is greater than the median so traverse upwards binarySearch(key: key, iminIndex: Int(midIndex) + 1, imaxIndex: imaxIndex) } else if midNumber == key { //Found it!
print("Found it at index \(midIndex)")} else {
print("Value \(key) not found")
}
}
このアルゴリズムの大部分は最初の方にありますが、配列から無関係な範囲を破棄して、ターゲット値を見つけるまで半分にし続けると、徐々に平らになっていきます。
以下のグラフを通して、ほとんどのアルゴリズムが、小さいデータセットでは同様のパフォーマンスを持っているが、データが大きくなるにつれて連続的に異なっていることを簡単に比較することができます。
このようにビッグ O 記法の他のタイプもありますが、次回に説明したいと思います。 では、また！
。