Berkeley CS 61B Data Structures(in Java) Homework5 加分+讨论帖

做了好久。。。。感觉Homework越来越难了。。。。

whdawn 发表于 2015-5-1 18:15
做了好久。。。。感觉Homework越来越难了。。。。

可不可以请教下怎样在union中怎样实现O(this.cardinality() + s.cardinality())的时间复杂度啊？
我本来想的是对s中每一个dlistnode都用调用insert（）方法，但那样时间复杂度就是 this.cardinality() * s.cardinality()的关系了。。。。。

amyzen 发表于 2015-5-10 10:55
可不可以请教下怎样在union中怎样实现O(this.cardinality() + s.cardinality())的时间复杂度啊？
我本来 ...

这种调用不能算两个复杂度相乘啊，union就是要调用insert的，这种情况是复杂度相加的

whdawn 发表于 2015-5-10 23:42
这种调用不能算两个复杂度相乘啊，union就是要调用insert的，这种情况是复杂度相加的

Hi
我想我们是不是我们insert（）的复杂度不一样呢？我insert（）的时间复杂度就已经是this.cardinality() 了，然后s的每个node如果都用一次insert（），就是相乘的关系了。。。

另外，union（）方法中，我试图把在DListNode中implement Comparable<Integer> 这个接口，使每个DListnode都是comparable的，然后把s和this连接成一个list，然后用sort()方法排序这个list，最后去除重复，想问下是这个思路么？

amyzen 发表于 2015-5-11 07:25
Hi
我想我们是不是我们insert（）的复杂度不一样呢？我insert（）的时间复杂度就已经是this.cardinalit ...

可以试试这个方法~         

终于做完了，有两个难点，卡了好久：1.发现各种protected的 prev， head等都不能用，开始用next（），item（）等方法都不习惯
2.时间复杂度要求是相加的关系，就不可以简单的调用insert（）方法遍历this了


sort（）可以实现相加的复杂度要求，但用sort（）方前，还在DListnode写了实现comparable（）接口，还是各种generics报错。。。。
后来union那考虑到s和this都已经是排好序的额，所以直接从s的list的front（）开始比大小，插到合适位置后，再移到s的下一位时就不需要比较this中已比较过的那些节点了，所以复杂度可以达到相加关系，还是学到很多~~~

另外还有学到了comparable也是种可以cast的类型

hw5依然写了好久……
继续加油，跟上进度！
求学分~

终于做完了。。。
part I 还蛮简单的，就是前面的作业改改就行了。
part II 光是题目意思就看了好久，也不知道什么是comparable对象，cs基础实在太差。。。
另外由于这次代码比以前的封装性较好，好多field都不能直接调用，还会抛出exception。
另外，从论坛里知道了时间复杂度这个概念。。。
其实如果想明白了，这次作业应该也不难的，关键还是经验不够吧。

终于做完了。。。给自己鼓掌，要进入data structure部分的学习了

[url=]

[/url]

想问下两个List中的node应该如何比较大小啊？怎样转换object类型的item啊？谢谢了~