问题描述
设置（MySQL的）：
Set up(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 |
+----+-------------+-------+--------+---------------+--------+---------+---------------------+------+-------------+
这是对我的previous后一个BFS的解决方案：
This is a BFS solution for my previous post:
http://stackoverflow.com/questions/2076715/challenge-how-to-implement-an-algorithm-for-six-degree-of-separation
但是，什么是它的复杂性？假设有完全 N 的记录。
But what's the complexity of it?Suppose there are totally n records .
推荐答案
假设有N个顶点和E边。对于每一个表可以有每对顶点之间的连接，需要检查所有顶点平等。因此，在最差情况下的性能将是O（| V | + | E |）
Assuming there are N vertices and E edges. For every table there can be a join between every pair of vertices and need to check all the vertices for equality. So worst case performance will be O(|V| + |E|)
更新时间：如果你正在考虑MySQL中有很多事情影响的复杂性，如果你有在球场上主键索引，B-tree索引将被使用。如果它的正常非集群索引，散列索引将被使用。有对每个这些数据结构的不同的成本。
Updated:If you are considering Mysql, there are lot of things that affect the complexity, if you have primary key index on the field, b-tree index will be used. If its a normal unclustered index, hash index will be used. There are different costs for each of these data structures.
从您的其他问题，我认为这是你的要求1.计算从UserX到UserY路径2.对于UserX，计算出不超过3步之遥的所有用户。
From your other question, I see this is your requirements1. Calculate the path from UserX to UserY2. For UserX,calculate all users that is no more than 3 steps away.
对于第一个，最好的办法是应用djikstra算法，并在Java构建一个表，然后在表中更新。需要注意的是，每次添加新节点，需要完整的处理。
For the first one, best thing is to apply djikstra algorithm and construct a table in java and then update it in the table. Note that, adding every new node, needs complete processing.
其他的解决方案，这将是使用SQL 1999标准引入了递归SQL创建一个包含从UserX到UserY的路径图。让我知道如果你需要递归查询参考。
Other solution to this will be to use recursive SQL introduced in SQL 1999 standard to create a view containing the path from UserX to UserY. Let me know if you need some references for recursive queries.
有关第二个，查询您已完全写的作品。
For the second one, the query you have written works perfectly.
这篇关于时间复杂度/ MySQL的性能分析的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！