时间复杂度/MySQL性能分析

Question

设置（MySQL）：

create table inRelation(
    party1 integer unsigned NOT NULL,
    party2 integer unsigned NOT NULL,
    unique (party1,party2)
);

insert into inRelation(party1,party2) values(1,2),(1,3),(2,3),(1,4),(2,5),(3,5),(1,6),(1,7),(2,7),(5,7);

mysql> select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+--------+--------+--------+--------+--------+--------+
| party1 | party2 | party1 | party2 | party1 | party2 |
+--------+--------+--------+--------+--------+--------+
|      1 |      2 |      2 |      5 |      5 |      7 |
|      1 |      3 |      3 |      5 |      5 |      7 |
+--------+--------+--------+--------+--------+--------+
2 rows in set (0.00 sec)

mysql> explain select * from inRelation a
    -> join inRelation b on a.party2=b.party1
    -> join inRelation c on b.party2=c.party1
    -> where a.party1=1 and c.party2=7;
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
| id | select_type | table | type   | possible_keys | key    | key_len | ref                 | rows | Extra       |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
|  1 | SIMPLE      | b     | index  | party1        | party1 | 8       | NULL                |   10 | Using index |
|  1 | SIMPLE      | a     | eq_ref | party1        | party1 | 8       | const,news.b.party1 |    1 | Using index |
|  1 | SIMPLE      | c     | eq_ref | party1        | party1 | 8       | news.b.party2,const |    1 | Using index |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+

这是我上一篇文章的 BFS 解决方案：

挑战，如何实现六度分离的算法？

但是它的复杂度是多少？假设总共有 n 条记录。

Answer 1

假设有N个顶点和E条边。对于每个表，每对顶点之间都可以存在连接，并且需要检查所有顶点是否相等。因此最坏情况下的性能将是 O(|V| + |E|)

更新：
如果你正在考虑Mysql，有很多因素会影响复杂性，如果你在字段上有主键索引，就会使用b树索引。如果是普通的非聚集索引，就会使用哈希索引。这些数据结构中的每一个都有不同的成本。

从你的另一个问题，我看到这是你的要求
1.计算UserX到UserY的路径
2. 对于UserX，计算距离不超过3步的所有用户。

对于第一个，最好的办法是应用 djikstra 算法并在 java 中构造一个表，然后在表中更新它。请注意，添加每个新节点都需要完整的处理。

对此的其他解决方案是使用 SQL 1999 标准中引入的递归 SQL 来创建包含从 UserX 到 UserY 的路径的视图。如果您需要一些递归查询的参考，请告诉我。

对于第二个，您编写的查询完美运行。