两个有序数组中找第n个数（其中n小于任何一个数组的长度）

klux

原帖由 绿衣 于 23-5-2009 23:43 发表

                               
登录/注册后可看大图

如果说对O(n)还有感觉的话，可是n^2、 lgN和更复杂的..具体是怎么算出来的有比较容易掌握的方法吗？很多书和资料只给出个复杂度是多少，实在让我为难啊

说明你看的书不好
有空的话看introduction to algorithm，没空的话就看看wiki吧

coredump

Notation	Name	Example
登录/注册后可看大图	constant	Determining if a number is even or odd; using a constant-size lookup table or hash table
登录/注册后可看大图	inverse Ackermann	Amortized time per operation using a disjoint set
登录/注册后可看大图	iterated logarithmic	The find algorithm of Hopcroft and Ullman on a disjoint set
登录/注册后可看大图	log-logarithmic	Amortized time per operation using a bounded priority queue[4]
登录/注册后可看大图	logarithmic	Finding an item in a sorted array with a binary search
登录/注册后可看大图	polylogarithmic	Deciding if n is prime with the AKS primality test
登录/注册后可看大图	fractional power	Searching in a kd-tree
登录/注册后可看大图	linear	Finding an item in an unsorted list; adding two n-digit numbers
登录/注册后可看大图	linearithmic, loglinear, or quasilinear	Performing a Fast Fourier transform; heapsort, or merge sort
登录/注册后可看大图	quadratic	Multiplying two n-digit numbers by a simple algorithm; adding two n×n matrices; bubble sort, shell sort,quicksort, or insertion sort
登录/注册后可看大图	cubic	Multiplying two n×n matrices by simple algorithm; finding the shortest path on a weighted digraph with theFloyd-Warshall algorithm; inverting a (dense) nxn matrix using LU or Cholesky decomposition
登录/注册后可看大图	polynomial or algebraic	Tree-adjoining grammar parsing; maximum matching for bipartite graphs (grows faster than cubic if and only if c > 3)
登录/注册后可看大图                                 登录/注册后可看大图	L-notation	Factoring a number using the special or general number field sieve
登录/注册后可看大图	exponential orgeometric	Finding the (exact) solution to the traveling salesman problem using dynamic programming; determining if two logical statements are equivalent using brute force
登录/注册后可看大图	factorial or combinatorial	Solving the traveling salesman problem via brute-force search; finding the determinant with expansion by minors. The statement                                 登录/注册后可看大图 is sometimes weakened to                                 登录/注册后可看大图 to derive simpler formulas for asymptotic complexity.
登录/注册后可看大图	double exponential	Deciding the truth of a given statement in Presburger arithmetic

key

原帖由 coredump 于 24-5-2009 10:52 发表

                               
登录/注册后可看大图

NotationNameExample

                               
登录/注册后可看大图

constantDetermining if a number is even or odd; using a constant-size lookup table or hash tablehttp://upl ...

背O()呀？
推荐看＜Data Structures, Algorithms, and Applications in C++＞，Sartaj Sahni，
中文版＜数据结构、算法与应用－－C＋＋语言描述＞，机械工业出版社，汪诗林等译
这本书第二章 程序性能中对于时间复杂性的讨论比较好，有空可以看一下。

然后就是klux说的MIT的Introduction to Algorithm，但这本书主要是数学计算，不头昏可以看一下