データ構造とアルゴリズム分析学習とアルゴリズム分析の方法について簡単に述べる.
6097 ワード
一、前言
データ構造とアルゴリズム分析はプログラマーの内功であり、コンピュータの世界を理解するにはデータ構造とアルゴリズムを理解しなければならないと言われていますが、これも議論されています.多くのビジネスニーズはデータ構造とアルゴリズムを使用できないため、JavaのArrayListやLinkedListなど、パッケージされたライブラリが直接呼び出すことができます.add、removeなどの方法では,内部実装に注目することなく,挿入削除などの基本操作を完了し,ビジネスロジックを実現できる.同じものが役に立つかどうかは、使うかどうかによって測ることができるとすれば、ビジネスロジックだけを書くのは確かに卵の役に立つことではありませんが、個人的には自分に役に立つかどうかによって判断され、自分に役に立つと思います==これは私に役に立ちます.
正直に言うと、自分が最初に企業面接の準備をして勉強しようとしたデータ構造とアルゴリズム(ネットで活動しているうちに『データ構造とアルゴリズム分析Java言語記述』を買って冬休みに見ようとした)を、その間にも多くの文章を読んだことがあり、開復さんはアルゴリズムの重要性を書いたことがあります.当時からアルゴリズムを知っている人はすごいと思っていました.しかし、本当にデータ構造とアルゴリズムを重視し始めたのはLeetcodeの最初のテーマTwoSumです.
1つの配列と1つの得数を指定し、配列内の2つの数値の加算が得数に等しい2つの数値のインデックスexampleを返します.
私の解法
他人の解法
すべて実行できますが、明らかに他の人の解法は私の優雅さより多すぎます.私の考えは2つのサイクルで窮屈にして、他の人はHashMapを使ってデータを格納して、しかもサイクルの中で同時に挿入と判断を行って、時間の複雑度は私のO(n 2)で、他の人のはO(n)で、データの規模が大きいならば、運行時間は大きく違います.同じ問題を見ることができて、異なる人が取った解決方法は違いを体現することができて、これはデータの構造とアルゴリズムに関係します
現在、データ構造とアルゴリズムに対する理解データ構造:問題を解決するために採用されたより効率的なデータ組織方式アルゴリズム:問題を解決するために採用されたより迅速なプログラム設計思想
技術分野で10年間戦いたい菜鳥として、データ構造とアルゴリズムを学ぶ必要がある.「データ構造とアルゴリズムJava言語記述」という本は半分読んだが、後ろの本はよく読めず、前の本は忘れてしまったので、まとめる必要があると思った.ネット上でもこの本の前の2章の内容のデータ構造とアルゴリズムの分析を非常に詳しくまとめた人がいます(一):基礎アルゴリズムの分析、ここで車輪を作らないで、いくつかの印象を深めたい内容だけをまとめました.
二、アルゴリズム分析の方法
(一)分析前提
計算モデル:無限メモリを持つモデルマシンがいずれの簡単な作業をしても時間単位が適切であり、マトリクス求逆やソートなどの想像操作が存在しないと仮定します.
(二)分析重点
1.実行時間(時間複雑度)影響因子:入力サイズn及び使用アルゴリズム2.メモリ占有(空間複雑度)影響因子:アルゴリズム自体の記憶占有、入出力データ占有及びアルゴリズム実行過程の一時占有
(三)時間複雑度計算——大Oマーク法(運転時間の上界、定数項と低次項の簡略化に注意)
Excample:ΣNi=0 i 3の運転時間を計算する
すべての宣言は、時間の3行目と6行目がそれぞれ1つの時間単位を占める5行目が1回ごとに4つの時間単位(2回の乗算、1回の加算、1回の付与)を占有し、N回の合計4 N個の時間単位を実行する4行目の初期化iが1つの時間単位を占有し、テストi<=nがN+1個の時間単位、i++自己加算がN個の時間単位となる合計2 N+2個の時間単位は呼び出し方法と戻り値のオーバーヘッドを無視し、合計6 N+4個の時間単位であるため、この方法はO(N)である
高速判断法則:1.forサイクル1つのforサイクルの実行時間は、テストを含むforサイクル内部の文の総実行時間に反復の回数を乗じたものが多い.2.ネストされたforサイクルは内側から外側に、ネストされたループのセット内の文の合計実行時間は、その文の実行時間にそのグループのすべてのforループのサイズの積を乗じる3.順序文の各文の実行時間と4.if/else文のif/else語の実行時間が判断の実行時間を超えない+if文/else文の長い実行時間を求める
分析の基本戦略は、内部(または最も深い部分)から外部に展開されます.メソッド呼び出しがあれば、まずメソッド呼び出しを分析します.再帰過程があれば、具体的な状況を具体的に分析する.
(四)空間複雑度計算
アルゴリズム占有空間サイズがデータ量nに従って変化しない場合、その空間複雑度はO(1)と記すことができ、アルゴリズム占有空間サイズがデータ量nに従って変化して線形に変化する場合、その空間複雑度はO(n)と記すことができる.
プログラム開発において,我々が指す複雑度は特に説明しない場合,時間複雑度を指す.現在のハードウェアの発展速度が速いため、アルゴリズムが占めるメモリを完全に考慮する必要がなく、通常は空間で時間を交換することができます.加えてアルゴリズムの空間的複雑度は計算しにくいため,我々は時間的複雑度に重点を置いている.
三、データ構造とアルゴリズム分析学習目標
学習は、問題の解決を導くために、1.問題に遭遇した場合に適切なデータ構造を迅速に選択できるように、さまざまなデータ構造の構造的性質を理解する2.各アルゴリズムの性能と応用シーンを理解し、問題に遭遇した場合に適切なアルゴリズムを迅速に選択できるようにする
参考資料及び資源サイト「データ構造とアルゴリズム分析:Java言語説明」データ構造とアルゴリズム動的可視化中国語サイトデータ構造とアルゴリズム/leetcode/lintcode題解
データ構造とアルゴリズム分析はプログラマーの内功であり、コンピュータの世界を理解するにはデータ構造とアルゴリズムを理解しなければならないと言われていますが、これも議論されています.多くのビジネスニーズはデータ構造とアルゴリズムを使用できないため、JavaのArrayListやLinkedListなど、パッケージされたライブラリが直接呼び出すことができます.add、removeなどの方法では,内部実装に注目することなく,挿入削除などの基本操作を完了し,ビジネスロジックを実現できる.同じものが役に立つかどうかは、使うかどうかによって測ることができるとすれば、ビジネスロジックだけを書くのは確かに卵の役に立つことではありませんが、個人的には自分に役に立つかどうかによって判断され、自分に役に立つと思います==これは私に役に立ちます.
正直に言うと、自分が最初に企業面接の準備をして勉強しようとしたデータ構造とアルゴリズム(ネットで活動しているうちに『データ構造とアルゴリズム分析Java言語記述』を買って冬休みに見ようとした)を、その間にも多くの文章を読んだことがあり、開復さんはアルゴリズムの重要性を書いたことがあります.当時からアルゴリズムを知っている人はすごいと思っていました.しかし、本当にデータ構造とアルゴリズムを重視し始めたのはLeetcodeの最初のテーマTwoSumです.
1つの配列と1つの得数を指定し、配列内の2つの数値の加算が得数に等しい2つの数値のインデックスexampleを返します.
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
私の解法
public class Solution {
public int[] twoSum(int[] nums, int target) {
int result[] = new int[2];
for(int x = 0;xfor(int y = x+1;yif((nums[x]+nums[y])==target){
result[0] = x;
result[1] = y;
}
}
}
return result;
}
}
他人の解法
public int[] twoSum(int[] numbers, int target) {
int[] result = new int[2];
Map map = new HashMap();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
result[1] = i + 1;
result[0] = map.get(target - numbers[i]);
return result;
}
map.put(numbers[i], i + 1);
} return result;
}
すべて実行できますが、明らかに他の人の解法は私の優雅さより多すぎます.私の考えは2つのサイクルで窮屈にして、他の人はHashMapを使ってデータを格納して、しかもサイクルの中で同時に挿入と判断を行って、時間の複雑度は私のO(n 2)で、他の人のはO(n)で、データの規模が大きいならば、運行時間は大きく違います.同じ問題を見ることができて、異なる人が取った解決方法は違いを体現することができて、これはデータの構造とアルゴリズムに関係します
現在、データ構造とアルゴリズムに対する理解データ構造:問題を解決するために採用されたより効率的なデータ組織方式アルゴリズム:問題を解決するために採用されたより迅速なプログラム設計思想
技術分野で10年間戦いたい菜鳥として、データ構造とアルゴリズムを学ぶ必要がある.「データ構造とアルゴリズムJava言語記述」という本は半分読んだが、後ろの本はよく読めず、前の本は忘れてしまったので、まとめる必要があると思った.ネット上でもこの本の前の2章の内容のデータ構造とアルゴリズムの分析を非常に詳しくまとめた人がいます(一):基礎アルゴリズムの分析、ここで車輪を作らないで、いくつかの印象を深めたい内容だけをまとめました.
二、アルゴリズム分析の方法
(一)分析前提
計算モデル:無限メモリを持つモデルマシンがいずれの簡単な作業をしても時間単位が適切であり、マトリクス求逆やソートなどの想像操作が存在しないと仮定します.
(二)分析重点
1.実行時間(時間複雑度)影響因子:入力サイズn及び使用アルゴリズム2.メモリ占有(空間複雑度)影響因子:アルゴリズム自体の記憶占有、入出力データ占有及びアルゴリズム実行過程の一時占有
(三)時間複雑度計算——大Oマーク法(運転時間の上界、定数項と低次項の簡略化に注意)
Excample:ΣNi=0 i 3の運転時間を計算する
public static int sum(int n) {
int partialSum;
partialSum = 0;
for(int i = 1; i <= n; i ++)
partialSum += i * i * i;
return partialSum;
}
すべての宣言は、時間の3行目と6行目がそれぞれ1つの時間単位を占める5行目が1回ごとに4つの時間単位(2回の乗算、1回の加算、1回の付与)を占有し、N回の合計4 N個の時間単位を実行する4行目の初期化iが1つの時間単位を占有し、テストi<=nがN+1個の時間単位、i++自己加算がN個の時間単位となる合計2 N+2個の時間単位は呼び出し方法と戻り値のオーバーヘッドを無視し、合計6 N+4個の時間単位であるため、この方法はO(N)である
高速判断法則:1.forサイクル1つのforサイクルの実行時間は、テストを含むforサイクル内部の文の総実行時間に反復の回数を乗じたものが多い.2.ネストされたforサイクルは内側から外側に、ネストされたループのセット内の文の合計実行時間は、その文の実行時間にそのグループのすべてのforループのサイズの積を乗じる3.順序文の各文の実行時間と4.if/else文のif/else語の実行時間が判断の実行時間を超えない+if文/else文の長い実行時間を求める
分析の基本戦略は、内部(または最も深い部分)から外部に展開されます.メソッド呼び出しがあれば、まずメソッド呼び出しを分析します.再帰過程があれば、具体的な状況を具体的に分析する.
(四)空間複雑度計算
アルゴリズム占有空間サイズがデータ量nに従って変化しない場合、その空間複雑度はO(1)と記すことができ、アルゴリズム占有空間サイズがデータ量nに従って変化して線形に変化する場合、その空間複雑度はO(n)と記すことができる.
プログラム開発において,我々が指す複雑度は特に説明しない場合,時間複雑度を指す.現在のハードウェアの発展速度が速いため、アルゴリズムが占めるメモリを完全に考慮する必要がなく、通常は空間で時間を交換することができます.加えてアルゴリズムの空間的複雑度は計算しにくいため,我々は時間的複雑度に重点を置いている.
三、データ構造とアルゴリズム分析学習目標
学習は、問題の解決を導くために、1.問題に遭遇した場合に適切なデータ構造を迅速に選択できるように、さまざまなデータ構造の構造的性質を理解する2.各アルゴリズムの性能と応用シーンを理解し、問題に遭遇した場合に適切なアルゴリズムを迅速に選択できるようにする
参考資料及び資源サイト「データ構造とアルゴリズム分析:Java言語説明」データ構造とアルゴリズム動的可視化中国語サイトデータ構造とアルゴリズム/leetcode/lintcode題解