  |
ある要素が、定義されたリストに存在するかみる場合は、前から順に見るから、その定義されたリストの要素数分かかるので、O(1)にはならない。
なので、その場合は、二重ループになるが、辞書を使うと、辞書のアクセスはO(1)だから、計算量削減できますね、ってことよ。
ただ、確かに言われてみると、
for element in ["りんご", "ごりら"]
for check in ["りんご", ”うんこ", "ごりら"]
if element == check { // この文字列の比較は、O(1)でできるのかというと、最悪計算量が文字列の長さに依存する、というのは言われてみるとそう。だが、うまく最適化されてO(1)でできるみたいだ。これは調べてみてほしいが、要素チェックの際に、文字列の長さ意識したことなかったわすまん。
}
一番愚直にリスト順繰り文字順繰り比較するアルゴリズムだと単語数n、単語の長さkとするとO(nk)になるだろ？kが本質でないとは？めちゃくちゃ長い単語だってあるよね？
定義されたリストも、["りんご", "うんこ", ...] とかなので、 要素の比較でよいので単語の長さは関係ない。別に部分文字列の一致の話をしていない。
いや関係あるよ何いってんだこいつ
ん？？？？？ 文字列の1文字1文字を比較するのか...? containsみたいな関数しらんのかもしかして... 面接もうこの時点でお前とは会話できんから落とすわすまんな
その関数はO(1)なの？
ある要素が、定義されたリストに存在するかみる場合は、前から順に見るから、その定義されたリストの要素数分かかるので、O(1)にはならない。 なので、その場合は、二重ループになる...
13
