C++相談室 part151

**デフォルトの名無しさん** · 2020/05/14(木) 11:53:25.59

C++に関する質問やら話題やらはこちらへどうぞ。
ただし質問の前にはFAQに一通り目を通してください。
IDE (VC++など)などの使い方の質問はその開発環境のスレにお願いします。

前スレ
C++相談室 part150
https://mevius.5ch.net/test/read.cgi/tech/1584975873/
このスレもよろしくね。
【初心者歓迎】C/C++室 Ver.105【環境依存OK】
http://mevius.5ch.net/test/read.cgi/tech/1556142878/

■長いソースを貼るときはここへ。■
　http://codepad.org/
　https://ideone.com/

[C++ FAQ]
https://isocpp.org/wiki/faq/
http://www.bohyoh.com/CandCPP/FAQ/ (日本語)

テンプレここまで

**デフォルトの名無しさん** · 2020/06/16(火) 23:21:49.71

>>435
キーの文字数Nはプログラムがビルドしおわったら変わらないのだから実質定数なのであって、
結局O(M)になるのでは…
（任意のxについて x + 定数 < a * xを満たす定数aを見出せるからオーダー表記の約束によりO(M+(定数)) = O(M)ェ、

しかもこの場合のMはデータの個数に比例するとわいえ、一般的はハッシュテーブルなら衝突しない限り
1回のテーブルアクセスで目的のエントリにたどり着くから、実際にはデータの個数÷ハッシュテーブルサイズ（エントリ数）
となるから衝突が無視できる（エントリ選択に統計的に偏りがなく、かつハッシュテーブルサイズが十分おおおきい
ならO(1)と逝って良いｷﾓｽ、

**デフォルトの名無しさん** · 2020/06/16(火) 23:31:56.61

あと1億文字のstring aと10文字のstring bとでハッシュキーを求める手間はどうかというと、
正直にやると文字数に比例するが
うまいことやったら定数にできる
もしくは文字列の構成時に都度ハッシュを更新するようにして、
ハッシュが入用になったときカタが付いている形ににする