線形配列、接続リスト、ソート、ナビゲーション、再帰関数

5384 ワード
データ構造 テキストリンク
一定時間(リスト長に関係なく):O(1)
線形時間(リスト長に比例):O(n)

🧱リニアアレイ


データ要素を順番に並べます.これは番号付きの格子に要素を埋め込む方法です.
ストレージスペースきおくくうかん:連続位置れんぞくいち
特定の要素の指定:非常に簡単なO(1)

🔧配置

  • ソート():ソートの新しいリストを取得します.内蔵関数
  • sort():対応するリストをソートします.リスト内のメソッド
    クリップ順序が間違っています.降順逆=True

    • 🪓ブラウズ(Searching)

  • 線形探索(順次探索Linear Search):順次行う.O(n)
  • バイナリ検索:検索するリストがソートされている場合にのみ適用されます.大きさ順に並べた性質を利用する.
    比較するたびに、リストを半分に減らします.O(log n)
    • バイナリ・ナビゲーションはリニア・ナビゲーションよりも速いが、必ずしもバイナリ・ナビゲーションを使用するわけではない.そう考えるには、まず配列を並べ替えて、一度だけ探索すれば、大きさ順に並べるよりも、毎回1回ひっくり返す方がいいです.

    💣さいきかんすう


    1つの関数で自分を呼び出して操作を実行するには、終了条件が重要です.
    再帰的な方法で多くの問題を解くことができる.ex)バイナリツリー、自然数の和、組合せ数、ハノイの塔、フィボナッチシーケンスを求めます
    再帰バージョンVS反復バージョン
    両方の関数はO(n)であるが,再帰関数は呼び出し関数により効率が低下する.
    再帰バイナリナビゲーション
    입출력 예

L = [2, 3, 5, 6, 9, 11, 15]
x = 6
l = 0
u = 6
L[3] == 6 이므로 3 을 리턴해야 합니다.

또 다른 예로,
L = [2, 5, 7, 9, 11]
x = 4
l = 0
u = 4
리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴해야 합니다.

    if x not in l、効率検査に失敗しました.
    このコードはLを迂回し、半分削除する必要があり、バイナリ検索の利点を解消します.xがLにない場合lowがupより大きい場合l>u

    🔨アルゴリズム複雑度


    問題を解決するには、どのくらいの時間ではなく、どのくらいのリソースが必要ですか.
  • 時間複雑度
    問題のサイズと解決時間の関係
  • 平均時間複雑度
    平均
    • (入力モードが任意であると仮定).
  • 最悪時間複雑度
    入力所要時間最大
  • 空間複雑度
    問題のサイズと問題解決に必要なメモリ容量の関係

    • 🔫Big-O Notation


    漸近表現(漸近表現)の一種で、ある関数の増分を別の関数との比較(アルゴリズムの複雑さを表す場合によく用いられる)として表す.
    入力サイズがnの場合、
    O(logn)-入力サイズのログに比例する所要時間
    O(n)-入力サイズに比例する時間
    係数は重要ではありません
  • 線形時間アルゴリズム-O(n)
    ex)線形探索アルゴリズム
    • を適用してn個のランダムにリストされた数字の中で最も高い値を検索する
  • ログ時間アルゴリズム-O(logn)
    ex)バイナリ検索アルゴリズムを適用して、n個の大きさ順の数字の中で特定の値
    • を検索する.
  • 非同期アルゴリズム-O(n 2)
    ex)挿入ソート(挿入ソート)
    Best case : O(n)
    Worst case : O(n2)
    • 複雑度が(より小さい)より優れているソートアルゴリズム

  • マージソート(merge sort)-O(nlogn)
    並べ替えたいデータを半分並べ替えます.

    • ちゅうしょうデータこうぞう


    内部実装を非表示にし、外部表示のみを提供

  • Data
    ex)整数、文字列、レコード、...

  • Aグループ演算子(一連の演算子)
    ex)挿入、削除、巡回、...
    ex)並べ替え、ブラウズ、...

    • 🔪リンクリスト

  • 演算定義
  • 特定の要素(k)
    • を参照してください.
  • リスト巡回
  • の長さ
    • を得る
  • 要素
    • を挿入
  • 要素
    • を削除
  • の2つのリストが
    • にマージされます.
    これは各要素を直列に接続して管理する方法です.
    要素はリンクと呼ばれるリングに接続され、中間から1つ削除されるか、中間から切断され、線形配列よりも他の要素(要素)を挿入します.
    エレメントを頻繁に挿入/削除するアプリケーションでは、接続リストがよく使用されます.
    短所
    1.構造に必要なストレージ容量(メモリ)が大きいことを示します.
    2.k番目の要素を探すには長い時間がかかります.
    線形配列では、データ要素が番号付きセルにあるため、この番号を使用できますが、接続リストでは要素がループで接続されているため、要素にアクセスするには、前からリンクごとに従う必要があります.
    ストレージスペース:任意の場所
    特定の要素の指定:非常に簡単なO(n)

    接続リスト要素の挿入


    def insertAt(self, pos, newNode):
    posはnewNodeが入る位置(1<=pos<=nodeCount+1)である.
  • newNodeの次のリンクを調整します(prev.next値はnewNodeのnextリンクを指します).
  • の前のノードprev(pos−1)のノードはnewNode(prev.nextはnewNode)を指す.
  • nodeCount+1.
    def insertAt(self, pos, newNode):
  prev = self.getAt(pos-1)
  newNode.next = prev.next
  prev.next = newNode
  self.nodeCount +=1
    1,2プロセスの順序は変更できません.prev.なぜなら、nextの値を先にnewNodeに置き換えると、本来指定した値は消えてしまうので、newNodeのnext値を指定することはできません.
    💡 注意事項

  • 挿入する位置は一番前にあります.
    prevは存在しません.頭部を調整する必要があります.

  • 挿入する位置が一番端の場合(一番前にposですべて検索する必要はなく、tailでprevをつかんで挿入するだけです).
    テイルの調整が必要

  • 空のリストを挿入する場合
    以上の2つの条件を処理すればいいです.
    💡 接続リスト要素の挿入の複雑さ
    一番前に挿入する場合:O(1)
    中間挿入:O(n)
    末尾に挿入する場合:O(1)

    • 接続リスト要素の削除


    def popAt(self, pos):
    posが指す位置(1<=pos<=nodeCount)

  • prev.curr次へ調整します.(prevはpos-1 currはposを表す)

  • curr(削除値)のデータを返します.

  • nodeCount -= 1
    💡 注意事項

  • 削除するノードは一番前にあります.
    prevは存在しません.頭部を調整する必要があります.

  • 削除するノードが最後尾の場合(tailの前のノード(prev)が見つからない場合は、最初から検索する必要があります)
    テイルの調整が必要

  • ユニークノードを削除する場合
    ->以上の2つの条件で処理しますか?!
    💡 接続リスト要素の複雑さの削除
    一番前から削除すると:O(1)
    中間から削除:O(n)
    上部から削除:O(n)

    • 2つのリストの接続


    def concat(self, L):
    別の接続リストLを接続リストselfの後ろに接続する
  • L1.concat(L2)
  • self.tail.next = L2.head#1番目のリストのtailは、2番目のリストのheadを指します.
  • self.tail = L2.tail#tail変更.

    • 💉接続リストを強調表示する利点(より柔軟に挿入および削除)


    指定したノードの後にノードを挿入または削除する方法を作成します.
    insertAfter(prev, newNode)
    popAfter(prev)
    ->一番前に挿入または削除する場合は、一番前にdummnodeを追加して、接続リストを少し変形させます.接続リストは0から始まります.

    変形した接続リスト要素を挿入


    def insertAfter(self, prev, newNode):
  • newNodeのnextは現在のprevのnextである
    newNode.next = prev.next
  • prevがtailである場合(挿入が最後尾の場合)、self.tailをnewNodeに移動します.
    if prev.next is None:
    self.tail = newNode
  • prevのnextはnewNode
    prev.next = newNode
  • nodeCountは1を増加し、Trueを返します.
    self.nodeCount += 1
    return True

  • InsertAtのインプリメンテーション:インプリメンテーションされたinsertAfter()を呼び出します.
    def insertAt(self, pos, newNode):
  • pos範囲条件確認
  • pos=1の場合、headの後に新しいノード
    • が挿入する.
  • pos=nodeCount+1の場合、prevをテール
    • として使用する
  • でなければprevはgetAt(~)

    • 変更された接続リスト要素の削除


    def popAfter(self, prev):
    prevの次のノードを削除し、そのノードのデータを返します.
    💡 注意事項
  • prevが最後のノードの場合(prev.next=None)
    削除するノードがありません
    return None
  • リスト末尾のノードを削除した場合(curr.next=None)
    Tail
    • を調整する必要があります

    変更された接続リストの接続


    最初のリストのtailを2番目のリストのスタックノードの後部ノードに接続する必要があります.
  • self.tail.next = L2.head.next
    元のリストを転送するtail
  • self.tail = L2.tail
    • [westeargram]login画面の実装
    [白俊5549]-Pithon