紹介する

開発の進度がますます深くなるにつれて、製品ユーザーのより高い段階の突破につれて、データ構造とアルゴリズムの重要性を発見し、Android開発エンジニアとして技術の発展につれて、Kotlin、NDK、Flutter、主流のフレームワークのソースコード、スレッドの同時など、あなたが身につけなければならない知識点がますます広くなることを発見します.しかし、これらの知識点はデータ構造とアルゴリズムから離れられません.アルゴリズム思考は技術オプションの際に自分のプロジェクトに適した枠組みに迅速に位置づけることができることを把握した.私たちが大学に通っていたとき、本でこの言葉を見たことがあります.データ構造+アルゴリズム=プログラムです.アルゴリズムとデータ構造の重要性を示し,この2つの課題を再確認した.

複雑さ

私たちはアルゴリズムの優劣とアルゴリズムの複雑さに密接に関係しています.では、複雑さとは何ですか.複雑度の計算ルールは何ですか?アルゴリズムはコンピュータタスクであり,入力データを加工処理して結果を得る過程である.アルゴリズムは計算の過程で2つの部分の資源を消費します:時間の資源、メモリの資源、私達もメモリの資源が空間の資源ですと言います.この計算タスクの過程で,消費されたリソースと入力されたデータ量は直接関係しているので,複雑度はデータ量Nに関する関数と呼ぶ.一般にO(n)などを用いて複雑さを表す.複雑度の計算ルールは次のとおりです.

複雑度が特定の定数に関係なく入力されたデータ量の配向が無限大である場合、定数が関数に及ぼす影響は無視できる.

多項式複雑度を加算する場合、結果としてO(n 2)+O(n)のように高く選択し、座標系図で指摘すると、Nがますます大きくなり、無限大になる傾向にある場合、O(n 2)の影響性が最も大きいことがわかります.

複雑さに及ぼす異なる計算方法の影響を容易に理解するために、入力された配列に対して、逆シーケンスの配列を出力するコードタスクを見てみましょう.例えば、a=[1,2,3,4,5]を入力し、[5,4,3,2,1]を出力する.
方法配列bを確立して初期化し、入力配列と等長の全ゼロ配列を得る.1つのforサイクルにより、a配列の要素を左から右に、b配列に右から左に割り当て、最後に配列bを出力して結果を得る.

  fun reverseArray(){
        val a:IntArray = intArrayOf(1,2,3,4,5)
        val b:IntArray = IntArray(5)
        for (i in a.withIndex()) {
            b[b.size-1-i.index] = i.value
        }

        b.forEach(::println)
    }

このコードはforループを用いて配列a中の要素を逆順序でb配列に格納し,その実行回数はa配列の長さと線形関係にあるため,時間複雑度はO(n)法2で配列の先頭要素を交換位置し,実現方式は以下の通りである.

 fun reverseArray2(){
        val a:IntArray = intArrayOf(1,2,3,4,5)
        val maxIndex = a.size-1
        for(i in 0..a.size/2){
            val tmp = a[i]
            a[i]=a[maxIndex-i]
            a[maxIndex-i]=tmp
        }

        a.forEach(::println)
    }

このアルゴリズムのサイクル計算回数はa.size/2であるため,時間的複雑度はO(n/2)であり,複雑度計算規則1によれば定数を無視した時間的複雑度はO(n)であるが,空間的複雑度は?空間的には,要素の個数に関係なく空間複雑度がO(1)である一時変数tmpを定義しただけである.

まとめ

前の解析から,時間的複雑さとコード構造が密接に相関し,空間的複雑さとデータ構造の設計が相関していることが分かった.