Saturday, 10 September 2011

Keep it simple, stupid! (O(n!) vs O(2^n)

Everything should be made as simple as possible, but no simpler.” - Albert Einstein

Độ phức tạp của thuật toán là cái gì đó rất phức tạp.
Để trả lời cho câu hỏi O(n!) và O(2^n) cái nào phức tạp hơn, tốt nhất đừng làm nó phức tạp thêm bằng 1 đống toán.
Thực nghiệm sẽ trả lời:
I love Python : đơn giản, nhẹ, đa nền tảng, interpreter (gõ lệnh vào trả kết quả ra luôn)

>>> from math import factorial
>>> factorial(100)
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000L
>>> print ''.join("{0} {1} {2}\n".format(n, 2**n, factorial(n)) for n in range(1,21))
1 2 1
2 4 2
3 8 6
4 16 24
5 32 120
6 64 720
7 128 5040
8 256 40320
9 512 362880
10 1024 3628800
11 2048 39916800
12 4096 479001600
13 8192 6227020800
14 16384 87178291200
15 32768 1307674368000
16 65536 20922789888000
17 131072 355687428096000
18 262144 6402373705728000
19 524288 121645100408832000
20 1048576 2432902008176640000

giờ thì ko phải nói thêm câu nào nữa.  Kết quả đã sờ sờ trước mắt :D