Determine the running time of an algorithm with two parameters

Question

I implemented an algorithm that uses two other algorithms to calculate the shortest path on a chart: Dijkstra and Bellman-Ford. Based on the time complexity of these algorithms, I can calculate the runtime of my implementation, which gives the code easily.

Now I want to experimentally verify my calculations. In particular, I want to build runtime based on input size (I follow the method described here below ). The problem is that I have two parameters - the number of edges and the number of vertices.

I tried to fix one parameter and change another, but this approach leads to two graphs - one for a different number of edges, and the other for a different number of vertices.

This leads me to my question - how can I determine the growth order based on two graphs? In general, how can we experimentally determine the complexity of the execution time of an algorithm that has more than one parameter?

Answer 1

It is very difficult at all.

, , ( O(1)) , log-log. log T vs. log N. n^k, k - . T(n) = n^{k log n} - , . T n, .

, - , n .

- , 3- , log-log-log .

, .

, T(n, m) = n^4 + n^3 * m^3 + m^4.

m = O(1), T(n) = O(n^4). n = O(1), T(n) = O(m^4). n = m, T(n) = O(n^6).

"" n, m, .

, m, n. , n = m - "" , .

, , / , - , . , , . - , , , .

Answer 2

, - (3- - ), , ( ) . , .

Matlab ( x y , .* - ):

x = log(parameter_x);
y = log(parameter_y);

% Find a least-squares fit
p = [x.^2, x.*y, y.^2, x, y, ones(length(x),1)] \ log(time)

, , , .

, , , , .

Answer 3

I was going to write my own explanation, but that would not be better than that .