Consider the C++ program fragments given below. Assume that n, m, and k are
unsigned integers and that the functions e, f, g, and h have the following
characteristics:
" The worst case running time for e(n,m,k) is O(1),
and it returns a value between 1 and (n+m+k).
"
The worst case running time for f(n,m,k) is O(n+m).
" The worst case running time for g(n,m,k) is O(m+k).
" The worst case running time for h(n,m,k) is O(n+k).
Determine a tight, big oh expression for the worst case running time of
each of the following program fragments:
------------------------------------------------------
(a). f(n, 10, 0);
g(n, m, k);
h(n, m, 10000);
------------------------------------------------------
(b). for (unsigned int i = 0; i < n; ++i)
f (n, m, k);
------------------------------------------------------
(c). for (unsigned int i = 0; i < e(n, m, k); ++i)
f (n, 10, 0);
------------------------------------------------------
(d). for (unsigned int i = 0; i < n; ++i)
for (unsigned int j = i; j < n; ++j)
f (n, m, k);
------------------------------------------------------
因為題目有點冗長，小弟把關鍵字標明了顏色
簡單說 就是要求這4小題的BigO，以下為小弟之答案
(a)
O(n+m+k)
------------------------------------------------------
(b)
O(n*(n+m))
------------------------------------------------------
(c)
O((n+m+k)*n)
------------------------------------------------------
(d)
O(n^3+n^2*m)
------------------------------------------------------
不知道 這樣的答案對不對
請高手解答!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.68.184.217
※ 編輯: fj90406 來自: 219.68.184.217 (03/22 16:55)
※ 編輯: fj90406 來自: 219.68.184.217 (03/22 16:56)