给定the person和list, constructing a BST for ancestors 的代价是多少?worst case O(n^2)对吗?
worst case O(n^2)???? 不会是 O(n^2) 啊? 不知道你哪里得到的这个时间复杂度的啊?
一个人大部分意义上来说都是 有父母的吧? 如果clone 这样的极端case 除外. 那么找相应的节点插入在BST 里面 最不济就是 O(n) 啊 咋 n square 呢?
时间主要是浪费在查找上了啊 咋会是 n square的 时间复杂度呢?
打个比方 如果给定一个 女士 是root的祖先 , 那你肯定要找右子树的最右边的节点, 那么这个时间复杂度就是 O(n) 吧?
最烂的应该是 O(n) 我想. N square 不知道是如何算出来的?
没有任何优势, 不如直接一遍一遍扫list,也是O(n^2), 空间开销更小,不需要BST
扫一个list 时间复杂度也是 O(n)啊 哪里出来的 O(n^2) 呢?
需要BST 意思就是一个2叉树 表示一个人的父母的关系. 不用2叉树 你用list ? 一个list 表示父亲那支儿? 一个list 表示母亲那支儿? 是这样吗?
如果这样的话 你不感觉麻烦? ^_^
也可能木有搞懂你的意思!
worst case O(n^2)???? 不会是 O(n^2) 啊? 不知道你哪里得到的这个时间复杂度的啊?
一个人大部分意义上来说都是 有父母的吧? 如果clone 这样的极端case 除外. 那么找相应的节点插入在BST 里面 最不济就是 O(n) 啊 咋 n square 呢?
时间主要是浪费在查找上了啊 咋会是 n square的 时间复杂度呢?
打个比方 如果给定一个 女士 是root的祖先 , 那你肯定要找右子树的最右边的节点, 那么这个时间复杂度就是 O(n) 吧?
最烂的应该是 O(n) 我想. N square 不知道是如何算出来的?
没有任何优势, 不如直接一遍一遍扫list,也是O(n^2), 空间开销更小,不需要BST
扫一个list 时间复杂度也是 O(n)啊 哪里出来的 O(n^2) 呢?
需要BST 意思就是一个2叉树 表示一个人的父母的关系. 不用2叉树 你用list ? 一个list 表示父亲那支儿? 一个list 表示母亲那支儿? 是这样吗?
如果这样的话 你不感觉麻烦? ^_^
也可能木有搞懂你的意思!