Give an example of an application that requires algorithmic content at the application level, and discuss the function of the algorithms involved.
给出在应用层需要算法内容的应用的一个例子,并讨论涉及的算法的功能。
Fingerprint matching algorithm used by forensics. Storing the fingerprints, and comparing them with the suspects prints it requires algorithms at application level. Function of algorithm is to have accurate matching and quick response.
Face Recognition.
Navigation: Shortest path.
Akinator is a web application that tells what was on our mind simply by asking questions. It uses Decision trees to come to conclusion. http://en.akinator.com/
导航,比如有时候会有最短路径算法;AI方面也很多,比如指纹解锁,人脸识别。
Suppose we are comparing implementations of insertion sort and merge sort on the same machine. For inputs of size n, insertion sort runs in 8n^2 steps, while merge sort runs in 64nlgn steps. For which values of n does insertion sort beat merge sort?
假设我们正比较插入排序与归并排序在相同机器上的实现。对规模为n的输入,插入排序运行8n^2步,而归并排序运行64nlgn步,问对哪些n值,插入排序优于归并排序?
Solve the function: 8n^2 <= 64nlgn, so n <= 43
n | 8n^2 | 64nlgn |
---|---|---|
2 | 32 | 128 |
3 | 72 | 304 |
4 | 128 | 512 |
10 | 800 | 2126 |
20 | 3200 | 5532 |
30 | 7200 | 9421 |
40 | 12800 | 13624 |
41 | 13448 | 14058 |
42 | 14112 | 14495 |
43 | 14792 | 14933 |
44 | 15488 | 15374 |
解方程 8n^2 <= 64nlgn, 所以 n <= 43
What is the smallest value of n such that an algorithm whose running time is 100n^2 runs faster than an algorithm whose running time is 2^n on the same machine?
n的最小值为何值时,运行时间为100n^2的一个算法在相同机器上快于运行时间为2^n的另一个算法?
Solve the function: 100n^2 <= 2^n, so n is at least 15
n | 100n^2 | 2^n |
---|---|---|
2 | 400 | 4 |
3 | 900 | 8 |
4 | 1600 | 16 |
10 | 10000 | 1024 |
14 | 19600 | 16384 |
15 | 22500 | 32768 |
解方程 100n^2 <= 2^n, 所以n最小是15
Follow @louis1992 on github to help finish this task. You can also subscribe my youtube channel.