分析以下循环的运行时间
Analyze the runtime of following recurrence
a.T(n)=T(n/2)+n;T(1)=1
因为我知道T(n)=2T(n/2)+n的运行时间是O(nlogn)，所以我认为答案是O(n^2)，但正确答案是O (n)
b.T(n)=2T(n/2)+1;T(1)=1
因为我知道T(n)=2T(n/2)+n的运行时间是O(logn)，所以我认为答案是O(log n)，但正确答案是O( n)
我真的很困惑，因为 T(n)='work per level' x 'number of levels'。
我认为b中的工作级别数是O(logn)。
使用技巧替换
...如果您看到 T(n / 2) 等术语
一）
b)
a.T(n)=T(n/2)+n;T(1)=1
因为我知道T(n)=2T(n/2)+n的运行时间是O(nlogn)，所以我认为答案是O(n^2)，但正确答案是O (n)
b.T(n)=2T(n/2)+1;T(1)=1
因为我知道T(n)=2T(n/2)+n的运行时间是O(logn)，所以我认为答案是O(log n)，但正确答案是O( n)
我真的很困惑，因为 T(n)='work per level' x 'number of levels'。 我认为b中的工作级别数是O(logn)。
使用技巧替换
...如果您看到 T(n / 2) 等术语
一）
b)