リーラ-クリシュナ
リーラ-クリシュナ

フォローしている

2019年4月1日•4分読み取り

swiftプログラミング言語で…

パート-1:

なぜデータ構造?

現代のアプリを作成するとき、アルゴリズムに固有の理論の多くは、しばしば見落とされています。 比較的少量のデータを消費するソリューションでは、特定の技術や設計パターンに関する決定は、単に物事を機能させるだけでは重要ではないかもしれま しかし、視聴者が成長するにつれて、データも成長します。 成功した大規模なハイテク企業の多くは、膨大な量のデータを解釈する相続人の能力です。 データの意味を理解することで、ユーザーは接続、共有、トランザクションの完了、意思決定を行うことができます。

→データ構造 :

  • 基本(基本)データ構造

スタック、キュー、ソートアルゴリズム

木&二分木、二分探索、ヒープ、ヒープソート、優先キュー

  • グラフ

グラフ、隣接リスト、dijkstraのアルゴリズム、primのアルゴリズム

→Big O表記法:

漸近解析はアルゴリズムの効率を記述するプロセスであり、Big O表記法と呼ばれる共通の形式で一般的に表現されている。

  • :

入力サイズ(n)が大きくなるにつれて、アルゴリズム(関数)を完了する時間。

  • :

アルゴリズム(関数)を実行するために必要なメモリ(スペース)の量。

これらはどちらも大きなO表記で表すことができます。

  • 最も一般的な時間の複雑さ:

→ 一定時間(O(1)) :-

一定時間アルゴリズムは、入力に関係なく同じ実行時間を持つものです。 このための大きなO表記はO(1)です。

→線形時間(O(n)) :-

線形時間アルゴリズムは、その速度が入力サイズに依存するものです。 言い換えれば、入力サイズ(n)が大きくなるにつれて効率が低下します。

→二次時間(O(n2)) :-

入力サイズの二乗に比例するまで時間がかかるアルゴリズムのことを指します。 入力サイズが大きくなると、すぐに制御がなくなります。

→対数時間(o(log n)) :-

O(log n)時間の複雑さを持つ一般的なアルゴリズムは、再帰関係がT(n/2)+O(1)であるバイナリ検索です。

→準線形時間(O(n log n)))) :-

アルゴリズムは、ある正の定数kに対してT(n)=O(n log^k n)の場合、準線形時間(対数線形時間とも呼ばれます)で実行されると言われます。

:

データ構造は、データを効率的に使用するためにデータを整理する体系的な方法です。 以下の用語は、データ構造の基礎用語です。

  • インターフェイス−各データ構造にはインターフェイスがあります。 Interfaceは、データ構造がサポートする一連の操作を表します。 インターフェイスは、サポートされている操作のリスト、受け入れることができるパラメータの型、およびこれらの操作の型を返すだけを提供します。
  • Implementation−Implementationはデータ構造の内部表現を提供します。 実装では、データ構造の操作で使用されるアルゴリズムの定義も提供されます。

→ データ構造の特性:

  • 正しさ-データ構造の実装は、そのインタフェースを正しく実装する必要があります。
  • 時間の複雑さ−データ構造の操作の実行時間または実行時間はできるだけ小さくする必要があります。
  • スペースの複雑さ−データ構造操作のメモリ使用量はできるだけ少なくする必要があります。

→ データ構造の必要性:

アプリケーションが複雑でデータが豊富になっているため、アプリケーションが今直面している三つの一般的な問題があります。

  1. データ検索−店舗の1万件(106件)の在庫を考えてみましょう。 アプリケーションがアイテムを検索する場合、検索を遅くするたびに1万件(106件)のアイテムを検索する必要があります。 データが大きくなると、検索が遅くなります。
  2. プロセッサ速度−プロセッサ速度は非常に高いですが、データが十億レコードに成長すると制限されます。
  3. 複数のリクエスト−何千人ものユーザーがwebサーバー上で同時にデータを検索できるため、高速サーバーでもデータの検索中に失敗します。

上記の問題を解決するために、データ構造が救助されます。 データは、すべての項目を検索する必要がないようにデータ構造で編成することができ、必要なデータをほぼ瞬時に検索することができます。

→swiftのスタックラッパーを見てみましょう:

swiftの配列の周りにラッパーを作成し、配列をストレージ構造として使用します。 配列は、配列の最後から実行されると、一定の時間(O(1))の挿入と削除を与えます。<5966><555>FIFO→First In First Outデータです。

: Uのスタック、元に戻す機能などがあります。

コメントを残す

メールアドレスが公開されることはありません。