アルゴリズム
(この文章は巴金督様の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としましょう.
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)比較エラーの場合は等号は使用できません
機能部(C++)
ベクトル ベクトル:可変配列かへんはいれつ
1)STLを関数パラメータ(値のコピー)とする
:vectorを関数のパラメータとして使用すると、値がコピーされるため、元の値は変更されません.
つまり、この場合は「参考者」を使うことができます. 2)STLを関数パラメータに渡す場合(時間的複雑さ)
:参照者を使用しない場合、ベクトルO(N)をコピーします.
参照者はアドレスしかスキップできないのでO(1)!
Cでは、文字列はchar配列であり、C/C++でStringとして使用される スペースを含む入力を受信した場合
:getline()、合計
scanf/printfおよびcin/cout
:機能に差はありませんが、cin/coutを使用する際の注意点があります.
1)
:C++ストリームを使用してCの標準I/Oと同期する
したがって、I/O量が大きいとタイムアウトする可能性があります.
対応するコマンドで同期を中断!でもcin/coutしか使えない!
2)
:cinとcoutのstreamを解く!
defaultは常にcinの前にcoutのバッファを空にします.
入力→出力→入力→出力が重複するように並べ替えます.
でも!これらの不要な接続を切断することで、coteは出力のみを表示するため、パフォーマンスが向上します.
ENDはオープンライン+出力バッファクリア機能ですが、パフォーマンスが悪いため、"n" を使用します.
の開発の鍵はクリーンコードですが、/開発の鍵は私の迅速な作成にあります.
:グローバル変数でも改行/総合ヘッダーなどを使用! 最後のスペースまたは改行を出力してもよい. デバッガは使用しないでください
:100行程度しかないので、鼻輪が締め付けられます.
ヘッダーは2 をブロックする可能性があります.
りろんぶん
[時間/空間の複雑さ]
:入力サイズとトラブルシューティング時間の相関
:指定した式を最大値の港湾表現を表す方法
(時間の複雑さを表す方法)
:1秒を基準に演算の複雑さによって大きく変化し,感覚だけでよい.
くうかんふくざつさ
:入力サイズと問題解決に必要なスペースの相関
アルゴリズムの問題はあまり気にしなくてもいいです.
512 MB=1.2億int変数.
[整数データ型]
: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を関数のパラメータとして使用すると、値がコピーされるため、元の値は変更されません.
つまり、この場合は「参考者」を使うことができます.
:参照者を使用しない場合、ベクトルO(N)をコピーします.
参照者はアドレスしかスキップできないのでO(1)!
[標準I/O]
: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は出力のみを表示するため、パフォーマンスが向上します.
[珂太は開発とは違う]
:グローバル変数でも改行/総合ヘッダーなどを使用!
:100行程度しかないので、鼻輪が締め付けられます.
<bits/stdc++.h>
:複数種類のヘッダーの統合-->実際のテープ上でもReference
この問題について(アルゴリズム), 我々は、より多くの情報をここで見つけました https://velog.io/@neity16/Algorithm-기초テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol