[TIL]複雑度、階調アルゴリズム

白駿サイトで問題を解いて、もっと勉強アルゴリズムが必要だと思ったので、追加学習の内容を整理しました.ユーチューブ(李可泰)では、「就職のためにコードしたスターだ」という講座を参考にした.

複雑さ

特定のアルゴリズムの性能を解析するために,時間的複雑さと空間的複雑さを解析した.
時間の複雑さ:特定のサイズの入力を分析するアルゴリズムの実行時間
空間複雑度:特定のサイズの入力に対して、アルゴリズムのメモリ使用状況を分析する
同じ機能を実行するアルゴリズムがあればあるほど,複雑度が低いほどよい.
複雑さが高いのは、時間やメモリが非常に必要だと言えます.

<複雑度マーキング法(bigoマーキング法)>

最速成長を考慮した港湾の標識法
関数の上限(最大値)のみを考慮します.極限の概念で考えると気持ちいいです.
bigoマーク法の手順と名称に従い、良い順から悪い順に以下のように整理します.
1(一定時間)-lonn(ログ時間)-N(線形時間)-Nogn(ログ線形時間)-N^2(二次時間)-N^3(三次時間)-2^n(指数時間)
一定時間:1つの繰り返し文
二次時間:二重文
質問でまず確認する内容は、時間制限(実行時間要件)です.
＜実行時間計測コード＞

import time
start_time=time.time()#측정 시작
#프로그램 소스 코드
end_time=time.time()#측정 종료
print("time:",end_time-start_time

グレースケールアルゴリズム

現在の状況で最適なシナリオを選択する方法
重要なのは,単純に最良に見えるものを選択しても最適解を見つけることができる正当性解析である.通常、グリディアルゴリズムは最適解を保証できないことが多い.
しかし,符号化テストによるグレッディアルゴリズム問題では,貪欲法で得られた解が最適解となった場合にのみ出題されることが多い.
コインの種類、最低でもコインで支払う問題

解決方法:大きな単位から探します.

正当性分析:大単位は小単位硬貨の倍数であり、大単位から探すと、支払う硬貨の数が減少する.
通貨の種類がKの場合,コードの時間的複雑度はO(K)である.

問題1)Nを1から引くかKに分ける.最小回数を求める

解決策:Nはできるだけ多く配分すればよい.

正当性分析:Nの大きい時間を減らして、2つ以上の数で1を割るのは1を使うよりもっと有効です

コード:入力された値NをKで除算するために、入力値//k*kで除算された数を作成し、nとの違いは1を減算した回数であり、countを加算する.除算された数をkで除算し、count+=1でnが1になるまでこの方法を繰り返します.繰り返し文を使用してnを減らす方法は、繰り返しごとにnをnで除算するため、kをnで除算するたびにチェックし、1を1で除算する方法が時間の複雑さよりも低いログの複雑さを決定することである.

注意:https://www.youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC