  |
もしわいが面接に出すなら、 単語の配列 ("りんご", "ごりら"...) があったとして、それらが、あらかじめ定義されてるリストとか辞書に入ってるか、をO(N)でチェックできますか、 みたい...
Nはリスト長？単語の長さは？単語の長さは？ねえ単語の長さは？？？
単語の長さ、という質問の意味がわからない (別に文字数は本質ではないので) が、Nは、単語の配列の要素数。Nが、100の場合と、10**6とかの場合でどうしたらいいですか、的な感じ。100の...
一番愚直にリスト順繰り文字順繰り比較するアルゴリズムだと単語数n、単語の長さkとするとO(nk)になるだろ？kが本質でないとは？めちゃくちゃ長い単語だってあるよね？
定義されたリストも、["りんご", "うんこ", ...] とかなので、 要素の比較でよいので単語の長さは関係ない。別に部分文字列の一致の話をしていない。
いや関係あるよ何いってんだこいつ
ん？？？？？ 文字列の1文字1文字を比較するのか...? containsみたいな関数しらんのかもしかして... 面接もうこの時点でお前とは会話できんから落とすわすまんな
その関数はO(1)なの？
ある要素が、定義されたリストに存在するかみる場合は、前から順に見るから、その定義されたリストの要素数分かかるので、O(1)にはならない。 なので、その場合は、二重ループになる...
36