问题 单项选择题

以下函数中渐进时间最小的是()。

A.T1(n)=2n+nlogn

B.T2(n)=n2+logn

C.T3(n)=2n+nlogn

D.T4(n)=n+10000logn

答案

参考答案:D

解析:

[要点解析] 通常情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作T(n)=O(f(n))。它表示随问题规模n的增大,算法执行的时间的增长率和f(n)的增长率相同,称为算法的渐进时间复杂度。当n→∞时,常见的渐进时间复杂度大小关系如下。

O(1)≤O(n)≤O(nlogn)≤O(n2)

由此可知,本试题选项中所给出的4个函数中,函数T4(n)=n+10000logn的渐进时间最小。

单项选择题

Many people consider the wider use of biofuels a promising way of reducing the amount of surplus carbon dioxide (CO2) being pumped into the air by the world’s mechanized transport. The theory is that plants such as sugar cane, maize (corn, to Americans), oilseed rape and wheat take up CO2 during their growth, so burning fuels made from them should have no net effect on the amount of that gas in the atmosphere.

Theory, though, does not always translate into practice, and just as governments have committed themselves to the greater use of biofuels, questions are being raised about how green this form of energy really is. The latest comes from the International Council for Science (ICSU) based in Paris.

The ICSU report concludes that, so far, the production of biofuels has aggravated rather than ameliorated global warming. In particular, it supports some controversial findings published in 2007 by Paul Crutzen of the Max Planck Institute for Chemistry in Germany. Dr. Crutzen concluded that most analyses had underestimated the importance to global warming of a gas called nitrous oxide (N2O). The amount of this gas released by farming biofuel crops such as maize and rape probably negates by itself any advantage offered by reduced emissions of CO2.

Although N2O is not common in the Earth’s atmosphere, it is a more potent greenhouse gas than CO2 and it hangs around longer. The result is that, over the course of a century, its ability to warm the planet is almost 300 times that of an equivalent mass of CO2.

N2O is made by bacteria that live in soil and water and, these days, their raw material is often the nitrogen-rich fertiliser that modern farming requires. Since the 1960s the amount of fertiliser used by farmers has increased sixfold, and not all of that extra nitrogen ends up in their crops. Maize, in particular, is described by experts in the field as a “nitrogen-leaky” plant because it has shallow roots and takes up nitrogen for only a few months of the year. This would make maize (which is one of the main sources of biofuel) a particularly bad contributor to global N2O emissions.

But it is not just biofuels that are to blame. The ICSU report suggests N2O emissions in general are probably more important than had been realised. Previous studies, including those by the International Panel on Climate Change (IPCC), a United Nations-appointed body of experts, may have miscalculated their significance — and according to Adrian Williams of Cranfield University, in Britain, even the IPCC’s approach suggests that the global-warming potential of most of Britain’s annual crops is dominated by N2O emissions.

Scientists realize that maize()

A. contributes little to global N2O emissions

B. absorbs nitrogen very efficiently in crops

C. is largely responsible for the surplus N2O

D. may experience a bad harvest for bacteria

单项选择题