题目内容

$f(n) = \log n$ is ___; $g(n) = 2n + 1$ is _; $h(n) = f(n) + g(n)$ is ___.

A. $O(n); O(n); O(n)$
B. $\Omega(n); O(n^2); O(n)$
C. $O(n); \Omega(n^2); O(n)$

查看答案

搜索结果不匹配？点我反馈

更多问题

An algorithm has running time $T(n)$, which satisfies $T(n) \leq T(n/2) + c$ and $T(2) \leq c$.Then its running time is _____.

A. $O(n \log n)$
B. $O(n)$
C. $O(1)$
D. $O(\log n)$

A binary tree is a rooted tree in which each node has at most two children.What is the relation between the number of nodes with two children $ n_1 $ and thenumber of leaves (the nodes without children) $ n_2 $ in a binary tree?

A. $ 2n_1=n_2 $
B. $ n_1=n_2 $
C. $ n_1+1=n_2 $

In Mergesort algorithm, we divide the input into three pieces of equal size( replace two pieces); solve the three subproblems on these pieces separately by recursion; and then combine the three results into an overall solution, spending only linear time for the initial division and final recombining.Then, the running time of the above algorithm is _____.

A. $O(n^{\log_2 3} \log n)$
B. $O(n^2 \log n)$
C. $O(n^{\log_2 3})$
D. $O(n\log n)$

Suppose we are given an instance of the minmum spanning tree problem on a graph $G$, with edge costs that are all positive and distinct. Let $T$ be a minimum spanning tree for this instance. Now suppose we replace each edge cost $c_e$ by its square $c_e^2$, thereby creating a new instance of the problem with the same graph but different costs. Decide whether you think the following statement is true or false.$T$ must still be a minimum spanning tree for this new instance.

A. 正确
B. 错误