2

はい/いいえの投票質問に対するユーザーの応答のMySQLテーブルがあります。このように見えます：

| user_id    | poll_id    | response
| 111        | 1         | 'yes'
| 111        | 2         | 'no'
| 111        | 3         | 'no'
| 222        | 1         | 'yes'
| 222        | 2         | 'yes'
| 222        | 3         | 'yes'
| 333        | 1         | 'no'
| 333        | 2         | 'no'
| 333        | 3         | 'no'

特定のuser_idについて、それらの応答と他のすべてのユーザーの応答との間の類似性を計算したいと思います。したがって、ユーザー111とユーザー222は0.333類似しており（3つの同じ応答のうち1つがあるため）、ユーザー111とユーザー333は0.666類似しています（3つの同じ応答のうち2つあるため）。

次に、特定のユーザーの類似度の中央値を決定し、それを他のすべてのユーザーの類似度の中央値に対してランク付けして、そのユーザーの「一意性」の尺度を考え出します。

この種の操作の時間計算量はどのくらいでしょうか？

*（注：現在、応答テーブルには約25,000のuser_id、400のpoll_id、および約500,000の行があります。明らかに、すべてのユーザーが各投票の質問に応答するわけではありません。時間計算量の計算に影響しますか？）*

4

2 に答える 2

2

ユーザーごとに、他のすべてのユーザーとの類似性を計算する必要があります。それはn2 -n 、または事実上n2です。ただし、中央値を見つけるには、これらの結果を並べ替える必要もあります。したがって、ソートがn log nであるとすると、支配的な項はn 2lognになります。

中央値ではなく平均値を使用すると、その種類を取り除くことができます。その場合、時間計算量はO（n 2）になります。

于 2012-04-26T14:35:07.303 に答える
0

n=ユーザーの数、p=投票の質問の数、=r応答テーブルの合計行とします。（あなたの場合、、、n = 25,000。）p = 400r = 500,000

1人のユーザーの場合、データベースはすべての応答を調べ、各ユーザーがハッシュルックアップを実行して、このユーザーの応答の1つと一致するかどうかを判断します。O(1)その場合、実行中の集計を追跡するのに時間がかかります。次に、そのユーザーの投票の質問を受け取り、簡単な合計を行います。回答の数が投票の質問の数よりもはるかに多い限り（あなたの場合）、これは回答を実行する時間によって支配されます。したがって、各ユーザーには時間がかかりますO(r)。ユーザーがnいるので、合計時間はO(n*r)です。

于 2012-04-26T14:45:42.913 に答える