アルゴリズム

4295 ワード

algorithm くうかんふくざつさ時間の複雑さテキストリンク

(この文章は巴金督様のhttps://www.youtube.com/watch?v=mBeyFsHqzHg&list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY&index=4を参照)

りろんぶん

[時間/空間の複雑さ]

コンピュータは毎秒3-5億(大まかな推定)

を行うことができる.

問題1~5秒かかる

時間の複雑さ
:入力サイズとトラブルシューティング時間の相関

bigoマーキング
:指定した式を最大値の港湾表現を表す方法
(時間の複雑さを表す方法)

近似時間複雑度とNの関係(非絶対)
:1秒を基準に演算の複雑さによって大きく変化し,感覚だけでよい.

くうかんふくざつさ
:入力サイズと問題解決に必要なスペースの相関
アルゴリズムの問題はあまり気にしなくてもいいです.
512 MB=1.2億int変数.

[整数データ型]

short/int/long/long long

:short型->3万個/int型->21億個(maple fulmesoの大きさです…!)

データ型が大きくなったときに使う順番
int(4 bバイト)->long long(8バイト)->符号なしlong long->string(このように大きい場合がある)

[エラーデータ型]

:float(4 bバイト)とdouble(8バイト)
doubleと書くのは誤差範囲やいろいろな面でいいので、実数=doubleとしましょう.

[覚えておきたい3つのこと]

1)実数の記憶/演算過程では,必然的に誤差が生じる.
(だから相対誤差の大きいdoubleを必ず使います!!)
    floatの有効数字は6ビット=相対誤差は10^-6までが安全です
    doubleの有効数字は15ビット=相対誤差は10^-15までが安全です
      ex)答えがNの場合2倍ならN-10^-15~N+10^-15まで!
2)doubleには、長範囲のすべての値を含めることはできません.
   (doubleは有効数字15ビット/longlongは19ビット)
3)比較エラーの場合は等号は使用できません

double a = 0.1+0.1+0.1;
double b = 0.3;
if(abs(a-b) < 1e-12) cout << "same" ;

:1 e-12=10^-12の意味!

機能部（C++）

[参照者]

:参照に基づいて演算を行う場合、ポインタを使用しなくてもよい

: 右側で参照子を使用した演算

[ STL (Standard Template Library) ]

ベクトル

ベクトル:可変配列かへんはいれつ
1)STLを関数パラメータ(値のコピー)とする

:vectorを関数のパラメータとして使用すると、値がコピーされるため、元の値は変更されません.
つまり、この場合は「参考者」を使うことができます.

2)STLを関数パラメータに渡す場合(時間的複雑さ)

:参照者を使用しない場合、ベクトルO(N)をコピーします.
参照者はアドレスしかスキップできないのでO(1)!

[標準I/O]

Cでは、文字列はchar配列であり、C/C++でStringとして使用される

スペースを含む入力を受信した場合

:getline()、合計

scanf/printfおよびcin/cout
:機能に差はありませんが、cin/coutを使用する際の注意点があります.
1) ios::sync_with_stdio(0)の作成
:C++ストリームを使用してCの標準I/Oと同期する
したがって、I/O量が大きいとタイムアウトする可能性があります.
対応するコマンドで同期を中断!でもcin/coutしか使えない!
2)cin.tie(0)の作成
:cinとcoutのstreamを解く!
defaultは常にcinの前にcoutのバッファを空にします.
入力→出力→入力→出力が重複するように並べ替えます.
でも!これらの不要な接続を切断することで、coteは出力のみを表示するため、パフォーマンスが向上します.

ENDはオープンライン+出力バッファクリア機能ですが、パフォーマンスが悪いため、"n"

を使用します.