在這兩種獲取 Linkedlist 中節(jié)點(diǎn)數(shù)的實(shí)現(xiàn)中，時(shí)間復(fù)雜度是否會發(fā)生變化？ private int getCountIterative() { Node start = head; int count = 0; while (start != null) { count++; start = start.next; } return count;}private int getCountRecursive(Node node) { if (node == null) return 0; return 1 + getCountRecursive(node.next);}
2 回答
溫溫醬
TA貢獻(xiàn)1752條經(jīng)驗(yàn) 獲得超4個(gè)贊
慕姐4208626
TA貢獻(xiàn)1852條經(jīng)驗(yàn) 獲得超7個(gè)贊
TL;DR：同樣的復(fù)雜性
要計(jì)算操作的復(fù)雜性（例如搜索或排序算法 - 或者您的示例，計(jì)數(shù)），您需要確定主導(dǎo)操作。
對于搜索和排序，通常是比較。你的主導(dǎo)業(yè)務(wù)是什么？假設(shè)它是node.next，查找下一個(gè)節(jié)點(diǎn)。
然后，這兩種方法都有O(n)操作 - 所以它的復(fù)雜性相同。
請注意，這個(gè)時(shí)間復(fù)雜度是一種簡化。有一些因素被忽略了，比如函數(shù)調(diào)用的開銷。因此，它具有相同的復(fù)雜性，但這并不一定會告訴您哪個(gè)版本更快。
添加回答
舉報(bào)
0/150
提交
取消