時間、空間の複雑さとBig O

時間と空間の複雑さを分析する重要性

アルゴリズムの効率を向上させ、最少の資源を使って、最高の効率

を達成する.

正しいデータ構造とアルゴリズムを選択する

.
Big O

ユーザは、アルゴリズムの時間と空間の複雑さを記述し、最悪の場合を指す

を指す.

は、入力長Nを与え、特に最悪の場合、アルゴリズムが費やす時間と空間上限

を指す.

は、アルゴリズムと入力サイズの関係を説明する

.
空間複雑度

アルゴリズムに必要なメモリサイズと入力Nの関係

は、nサイズの1次元配列を構築するために、メモリはO(n)であり、2次元配列はO(n 2)

である必要がある.
Big O計算方法

除去定数

.非主要因子を除去する

.

例:

O(N+8)=O(N)O(N 2+N)=O(N 2)
例題
フィボナッチ数
フィボナッチの数は、通常F(n)で表され、形成されたシーケンスをフィボナッチの数列と呼ぶ.この数列は0と1から始まります.後ろの各数字は前の2つの数字の合計です.つまり、
F(0)＝0、F(1)＝1 F(N)＝F(N−1)＋F(N−2)であり、N＞1はNを与え、F(N)を計算する.

func fib(N int) int {
    if N <= 0 {
        return 0
    }
    if N == 1 {
        return 1
    }
    return fib(N-1)+fib(N-2)
}

時間の複雑さが、ツリーノードの個数に再帰されると、時間複雑度上限O(20＋21＋22＋＋＋＋2 n−1)＝O(2 n−1)が、再帰式にM再帰的コールがある場合、時間複雑度はO(Mn)

である.

空間複雑度O(n)＊各レイヤの動作占有空間

検索テキストの挿入位置
順序配列と目標値を指定し、配列内で目標値を見つけ、インデックスを返します.ターゲット値が配列に存在しない場合は、順序で挿入される位置を返します.
配列に重複要素がないと仮定できます.
例1:

  : [1,3,5,6], 5
  : 2

解法-二分法を利用する:

func searchInsert(nums []int, target int) int {
    if len(nums) == 0{
        return 0
    }
    start := 0
    high := len(nums)-1
    for start <= high {
        mid := (start+high)/2
        num := nums[mid]
        if target == num{
            return mid
        }else if(target > num) {
            start = mid + 1
        } else {
            high = mid-1
        }
    }
    return start
}

時間の複雑度の2分の数の時間複雑さは、2の何乗がNに等しいかに依存し、時間複雑度O

である.
一般的なアルゴリズムの時間複雑度

低から高:O(1)、O(logN)、O(NlogN)、O(N 2)(E:辺、V:ノード)

アルゴリズム
時間の複雑さ
空間複雑度
深さ優先巡回
O(124)E 124＋124 V 124)
O(124 V 124)
広さ優先巡回
O(124)E 124＋124 V 124)
O(124 V 124)
クイックソート
O(N 2)
O(N)
並べ替え
O(NlogN)
O(N)
泡の並べ替え
O(N 2)
O(1)
並べ替えの挿入
O(N 2)
O(1)