The book says, because all the complexity, so the column, in a linear table, for example,)
The linear table time complexity:
Best case: O (1)
The worst: O (n)
Average: O (n/2)
And then give the average time complexity is O (n).

I thought that the average time complexity is, on average, the complexity of the cases, but it is O (n).
The result is only consider the worst case time complexity, or otherwise it method,
(PS: take the name of the average time complexity is really easy confused,)

CodePudding user response:

For the time complexity of n/2 and n times are 1 so can be seen as n
Like the n + 1 and n - 1 as a n is a truth
The highest time shall prevail

CodePudding user response:

reference 1st floor weixin_44521568 response:

n/2 for time complexity and the number of n is 1 so it can be regarded as n
Like the n + 1 and n - 1 as a n is a truth
Will be subject to the highest time

N is the main growth

CodePudding user response:

Average is that the worst (best +)/2, good,

Assuming that N, infinity, and time complexity, just the concept of a measurement, do not ask for precise Numbers,

The complexity of N/2, or N + m (m is far less than N) and so on, and we can approximate the task, complexity of N,

So is the average number of common complexity
O (N)
The O (1)
O (logN)
O (N ^ 2)
And so on,

CodePudding user response:

The worst thing is to calculate ah
Normal time array: O (n)
Hash table: O (1)
Fast row: O (logN)
Binary: O (log2N)
Complete backpack gauge: O (VP)
There are such as the complexity of O (N ^ 2)

Method:
Every time a operation to O (1)
Unknown maximum range for the data in brackets
Traversal, for example, an array of length N
The time complexity is: O (N)

Hope,,

CodePudding user response:

refer to 6th floor Slzde_sub response:

you only need to pay attention to the worst time complexity can

Quote: reference questions on 4th floor response:

Average is that the worst (best +)/2, good,

Assuming that N, infinity, and time complexity, just the concept of a measurement, do not ask for precise Numbers,

The complexity of N/2, or N + m (m is far less than N) and so on, and we can approximate the task, complexity of N,

So is the average number of common complexity
O (N)
The O (1)
O (logN)
O (N ^ 2)
And so on,

Who taught you the average is additive/2,,, I Buddha

Is a talent?

Even if I say wrong, I also am kind answer you ah,,, you don't have to satirize me, a little politeness.