多项式时间和指数时间 [英] Polynomial time and exponential time

问题描述

我有一个关于举例来说，如果一个算法需要Ø多项式时间算法，非多项式时间算法和指数时间算法之间的差异问题（N ^ 2）的时间，然后哪一类会是吗？

I have a question about the difference between polynomial time algorithms, non polynomial time algorithms and exponential time algorithms for example if an algorithm will take O(n^2) time then which category will it be in?

推荐答案

检查了这一点

<一个href="http://en.wikipedia.org/wiki/Big_oh#Orders_of_common_functions">http://en.wikipedia.org/wiki/Big_oh#Orders_of_common_functions

指数比多项式更糟糕。

为O（n ^ 2）落入二次范畴，它是一种类型的多项式的并优于指数（指数等于2的特殊情况下）。

O(n^2) falls into the quadratic category, which is a type of polynomial (the special case of the exponent being equal to 2) and better than exponential.

指数是的多的比多项式更糟糕。看功能如何生长

Exponential is much worse than polynomial. Look at how the functions grow

N = 10 100 1000

n = 10 100 1000

N ^ 2 = 100 10000百万

n^2 = 100 10000 1000000

K ^ N = K ^ 10 K ^ 100 K ^ 1000

k^n = k^10 k^100 k^1000

K ^ 1000是非常巨大的，除非k是不是有点像1.1小。像，像宇宙中的每一个粒子都必须做每秒100十亿十亿十亿运营的数十亿数十亿年万亿弄完。

k^1000 is exceptionally huge unless k is smaller than something like 1.1. Like, something like every particle in the universe would have to do 100 billion billion billion operations per second for trillions of billions of billions of years to get that done.

我没有计算出来，但它的那么大。

I didn't calculate it out, but ITS THAT BIG.

这篇关于多项式时间和指数时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！