算法与数据结构-各种循环的时间复杂度分析（英语）
前言
在英语面试中可能需要 用英语表达算法的时间复杂度，这篇博文是学习后自我训练的笔记，用学过的英语来描述算法的时间复杂度。
首先介绍如何用英语表达指数幂，然后是各种循环的复杂度分析。
How to express the exponent?
M to the power of N = M^N
x to the power of two thirds = (x)^(2/3)
x squared = x^2
x cubed = x^3
x plus y quantity squared = (x+y)^2
the sum of X one, X two and so on out to Xn, the whole string in parenthesis,raised to the second power = (x1 + x2 + x3 + ... + xn)^(2)
simple for-loop with an increment of size 1
for (int x = 0; x < n; x++) {
//statement(s) that take constant time
}
The initialization statement assign 0 to x runs once.
Java for loop increments the value x by 1 in every iteration.So the x is first 0,then 1,then 2,...,then n-1.
The increment statement xplusplus runs n times.
The comparison statement x is less than n runs n plus 1 time.
Summing them up, we get a running time complexity of for loop of n + n + 1 + 1 = 2*n + 2
The statements inside the loop runs n times, supposing these statements account for a constant running time of c in each iteration, they account for a running time of c*n throughout the loop's lifetime.Hence the running time complexity is XXX
for-loop with increments of size k
for (int x = 0; x < n; x+=k) {
//statement(s) that take constant time
}
The initialization statement runs once.
The incrementation part x+k runs floor(n/k) times
The comparision statement x The inside the loop runs c * floor(n/k) times. Summing them up, the running time complexity is 1 + n/k + n/k + 1 + c * n/k = (c+2)/k* n + 2 Dropping the leading constants (c+2)/k ==> n + 2 Dropping the lower order items ==> O(n) The inner loop runs (1+1+m+m)+c*m = (2m+2)+cm The outer loop runs (1+1+n+n) + n(2m+2+cm) = (2+c)nm+4n+2 ,which is O(nm) Let's start with the inner loop. The initialization statement j = 0 runs n times throughout the whole lifetime. The comparison statement j < i runs different times when i is set to different value. For example, the first time when i is 0,j
The increment statement j++ runs 0 + 1+2+...+n-1 times,which is (n-1)*n/2 The statement inside the inner loop runs also c(n-1)n/2 times As for the outer loop, the statements runs a total of 2n+2 times Hence, the running time complexity is n+(1+n）n/2 + (n-1)n/2 + c(n-1)n/2 + 2n+2 which is O(n^2) The initialization statement i=0 runs once; How much times dose the comparison statement i To calculate these, we should ignore the i++ after the first iteration. For example i is first 0 , i is then 1, then i is 2, then i is 4... until i is great than n. we assume n is greater than 2^k and less than 2^(k+1) so, the i *=2 statement runs k times, and the i < n statement runs k+1 times, which k is estimately log2(n). The statement j++ of the inner loop inside the outer loop runs 1+2+4+...+2^log2(n) = 2^(log(n)+1) - 1 = 2*n -1 times So the total times is (2n-1)2 + 2 + (2n-1)c Hence we can get the sum time of the code is 1 + 1 + 2(2n-1) + 2(2n-1) + 2+ (2n-1)*c The term linear in n dominates（支配了） the others and the time complexity is O(n). Note that the quiz can have a rough but not a tight bound approximation, that is the outer loop runs at most n times, the inner for-loop iterates at most n times each iteration of the outer loop. So we can conclude that the running time complexity is O(n^2).simple nested for-loop
for (int i=0; iNested for-loop with dependent variables
for (int i=0; iNested for-loop with index modification(a little bit hard)
for (int i=0; i