45日目TIL

開始します。

今日はよく使われるアルゴリズムと時間の複雑さを学びました.符号化テストの問題を解く際には,制限事項に時間的な複雑さがしばしば現れるが,不明であり,本章では概念を理解できる.

Algorithm

Time Complexity

Big-O（Big-O） Big-Ω（Big-Omega） Big-θ(ヴィック・セイタ)

以上の3つの時間的複雑さを表す方法は,それぞれ最悪,最良,中等(平均)の場合を表す.その中で最もよく用いられるのがBig-Oマーキング法であり、Big-Oマーキング法は最悪の場合を考慮しているため、プログラムの実行に要する最悪の時間を考慮することができる.「少なくとも時間がかかる」とか「こんなに時間がかかる」というよりも、「こんなに時間がかかるかもしれない」ということを考えてこそ、対応することができます.
O(1)
O(1)は定数複雑性と呼ばれ,入力値が増加しても時間は増加しない.

function O_1_algorithm(arr, index) { return arr[index]; } let arr = [1, 2, 3, 4, 5]; let index = 1; let result = O_1_algorithm(arr, index); console.log(result); // 2

O(n)
O(n)は線形複雑度と呼ばれ,入力値が増加するにつれて時間も同様の割合で増加することを意味する.

function O_n_algorithm(n) { for (let i = 0; i < n; i++) { // do something for 1 second } } function another_O_n_algorithm(n) { for (let i = 0; i < 2n; i++) { // do something for 1 second } }

O(log n)
O(logn)は対数複雑度と呼ばれ,Big‐Oマーキング法ではO(1)に次ぐ高速時間複雑度を持つ.
資料構造から学んだBSTはO(logn)の典型的な例である.
BSTでは,必要な値にナビゲートすると,ノードを移動するたびに状況の数が半分に減少する.理解しやすいゲームで例えるとup&downなどです.

プレイヤー1は、1から100の数字を1つ選択します(30が選択されたとします)。 50(中)個の数字は50未満を表すのでdownと言います。 これは1から50の数字で、再び状況の数を半分に減らすために、25を提案します。 25より大きいのでupと呼びます。 状況は半分に減り続け、正解を探している。 数字を出すたびに状況の数が半分に減るので、最悪の場合でも7回で欲しい数字を見つけることができます。 BSTにおける値ナビゲーションもO（logn）時間の複雑さを持つアルゴリズム（ナビゲーション方法）であり，論理的に同じである。

O(n^2)
O(n^2)は二次複雑性と呼ばれ,入力値が増加するにつれて時間がnの平方数の比率で増加することを意味する.

function O_quadratic_algorithm(n) { for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { // do something for 1 second } } } function another_O_quadratic_algorithm(n) { for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { for (let k = 0; k < n; k++) { // do something for 1 second } } } }

O(2^n)
O(2^n)は指数複雑度と呼ばれ,Big−Oマーキング法では最も遅い時間複雑度を持つ.

function fibonacci(n) { if (n <= 1) { return 1; } return fibonacci(n - 1) + fibonacci(n - 2); }

Greedy Algorithm

貪欲なアルゴリズムは、その名の通り、選択の瞬間ごとに、目の前の最良の状況だけを追求して、最終的な答えを達成する方法で、以下の手順で区分されています.
1.プログラムの選択:現在の状態でのベストアンサーを選択します.
2.適切性チェック:選択した解が問題の条件を満たしているかどうかをチェックします.
3.解答検査:元の問題が解決されたかどうかを検査し、解決されていない場合は、選択ステップに戻り、上記の手順を繰り返します.

탐욕 알고리즘 사례
김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였다.

이때 김코딩은 어떻게 거슬러 주어야 할까? 탐욕 알고리즘으로 동전의 개수를 헤아리는 일은, 우리가 일반적으로 거스름돈으로 동전을 선택하는 방법과 동일하다. 거스름돈 960원을 채우기 위해서 먼저, 500원짜리 동전을 한 개 선택한다. 그다음은 100원짜리 동전을 네 개 선택하고, 그다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택한다. 김코딩의 입장에 탐욕 알고리즘의 문제 해결 과정을 적용하면 다음과 같이 문제를 단계적으로 구분할 수 있다.

1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택한다.
2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한 후, 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택한다.
3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사하고 액수가 부족하면 1번 과정부터 다시 반복한다.

貪欲アルゴリズムは、以下の2つの条件の「特定の状況」を満たさない限り、貪欲アルゴリズムは最適解を保証できない.貪欲なアルゴリズムを適用するには,解決すべき問題は以下の2つの条件を備えなければならない.
-貪欲な選択プロパティ:前の選択は後の選択に影響しません.
-最適な部分構造:問題の最終的な解決方法は、部分的な問題の最適な解決方法から構成される.

の最後の部分

今日はSection 3で初めて公平なプログラミングを行いました.これは久しぶりに公平な交渉とパートナーが学ぶアルゴリズムを設計し理解するのに役立ちます.また,単純に答えを導くだけでなく,時間の複雑さを考慮してコードを修正し,どのアルゴリズムを用いて問題を解くことが有効であり,問題を解く過程で,今日学んだ内容を正確に理解できる.