アルゴリズム週間02

7810 ワード

アレイ


アレイは固定サイズのデータ空間です.一度決めたら変えられない!
配列はnumber[0]のように各要素にすぐにアクセスできます.
  • 要素の順序はゼロから始まり、インデックスと呼ばれます.
  • インスタントアクセスは、一定時間以内にアクセスできることを意味する.
    すなわち,O(1)内で接することができる.
  • 瓇アレイの間にエレメントを挿入/削除するには、すべてのエレメントを移動する必要があります.
    最悪の場合,配列の長さはNを移動しなければならないので,O(N)の時間的複雑さを持つ.
    配列は、新しい要素を追加するには、新しい空間を割り当てる必要があるため、非常に効率的な資料構造です.
  • Butpythonの場合、内部はダイナミック配列を使用しており、配列長が長くなってもO(1)の時間的複雑さが必要になるように設計されています!
  • pythonの並びはリンクリストとしても、並びとしても使える、効率的な資料構造です!
  • リンクリスト


    「リンク」リストには、サイズが指定されていないデータの領域が表示されます.絆さえ繋げば自由に伸ばせる!
    特定の要素にアクセスするには、「」リストが接続ループに沿ってナビゲートされます.
  • 最悪の場合、全ての元素を探索する必要があるため、O(N)の時間的複雑度を有する.
  • 接続リングをポインタと呼び、各要素をノードと呼ぶ.
  • エレメントを途中で挿入/削除するには、前後のポインタを変更するだけです.
  • したがって、要素挿入・削除はO(1)の時間的複雑度で行うことができる.
  • ArrayLinkedListは、特定の要素O(1)O(N)の間に削除O(1)O(1)を挿入してデータを追加する場合、すべてのスペースが満たされている場合は、すべてのスペースが満たされていても、最後のノードを動的に追加すれば、新しいメモリスペースを割り当てる必要があります.クリーンアップデータに頻繁にアクセスし、Arrayを使用するときに頻繁にデータを挿入および削除する場合は、LinkedListを使用することが望ましい.

    バイナリナビゲーション


    数字の範囲は,1から100までの出題者によって決定された数字のアルゴリズムである.
    答えを言えば、数字を答えるためにUPするかDownするかを教えてくれます
    アルゴリズムの観点から見ると、最も有効な方法は
    試行範囲の半分である50!
    答えがUPだと1~49が候補から消えてしまいます
    答えがDOWNなら、51~100は候補から消えるからだ.
    この方法はバイナリナビゲーションです.

    さいきかんすう


    再帰とは、何かを定義するときに自分を参照することです.
    再帰関数とは、自分の関数を呼び出すことです.

    知らない概念

  • 数値降下法を用いる//演算子は、小数点以下のすべての数字を切り捨ててシェアのみ表示することができる.
  •    >>> print((4 + 5) / 2)
       4.5
       >>> print((4 + 5) // 2)
       4
  • 文字列スライド
  • >>>"가나다라마바사"[0:3]
    '가나다'
    >>>"가나다라마바사"[0:-2]
    '가나다라마'
  • ソート
    並べ替えたい列の後ろにあります.sort()関数を呼び出すだけでいい!
  • >>> array = [4, 1, 6, 2]
    >>> array.sort()
    >>> array
    [1, 2, 4, 6]
    
    # 참고로 한글도 정렬 가능!
    >>> korean_array = ["라", "가", "다", "나"]
    >>> korean_array.sort()
    >>> korean_array
    ['가', '나', '다', '라']
  • set資料型
  • >>>a = set([1,2,3,4,5])
    >>>a
    {1, 2, 3, 4, 5}
    >>>b = {1,2,3}
    >>>b
    {1, 2, 3}