题目内容

If an algorithm has running time $T(n)= O(n\log n)$, then $T(n)$ may most likely satisfy that _____.

A. $T(n) = 4T(n/4) + O(n^2)$
B. $T(n) = 4T(n/4) + O(n) $
C. $T(n) = 3T(n/2)+O(n) $
D. $T(n) = 2T(n/2) + O(\log n)$

查看答案

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

更多问题

Under the same condition as exercise 3.Then, there is not a minimum spanning tree of [mathjaxinline]G[/mathjaxinline] that doesn’t contain the edge [mathjaxinline]e[/mathjaxinline].

Assume that each of the following sets are not equal. Which one is the biggest set?

A. P
B. NP
C. co-NP
D. EXP

If we have a magic machine that can solve 3-SAT problem in unit time. Which of the following problem can NOT be solve if we only use this machine polynomial times? (Assume P ≠ NP)

A. INDEPENDENT-SET
B. VERTEX-COVER
C. PRIMES
D. HALTING PROBLEM

Suppose we are given an instance of the [mathjaxinline]s-t[/mathjaxinline] shortest path problem on a directed graph [mathjaxinline]G[/mathjaxinline]. We assume that all edge cost are positive and distinct. Let [mathjaxinline]P[/mathjaxinline] be a minimum-cost [mathjaxinline]s-t[/mathjaxinline] path for this instance. Now suppose we replace each edge cost [mathjaxinline]c_e [/mathjaxinline] by its square, [mathjaxinline]c_e^2 [/mathjaxinline], 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.[mathjaxinline]P[/mathjaxinline] must still be a minimum-cost [mathjaxinline]s-t[/mathjaxinline] path for this new instance.[mathjaxinline]P[/mathjaxinline] must still be a minimum-cost [mathjaxinline]s-t[/mathjaxinline] path for this new instance.