时间复杂度/ 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-tree索引将被使用。如果它是一个正常的非集群索引，散列索引将被使用。存在用于每一个这些数据结构的不同的成本。

从您的其他问题，我看这是你的要求 1.计算从用户X到UserY路径 2.对于用户X，计算是不超过3个步骤远的所有用户。

有关的第一个，最好的办法是应用djikstra算法和在Java构造一个表，并然后在表更新。需要注意的是，加入每一个新的节点，需要完整的处理。

该另一解决方案将是使用在1999标准SQL引入递归SQL创建包含从用户X到UserY路径的图。让我知道如果你需要递归查询参考。

有关第二个，所述查询已完全写入作品。