0
Follow
2
View

# Find the execution times and time complexity

donglei2860 注册会员
2023-02-25 12:13

Part of the answer references GPT, GPT_Pro to solve the problem better
The function my_fun(i,k) is executed Tn+1, That is, Tn+1 of the outer for loop, and the time complexity of the program is O(Tn+1).

The specific program can be shown as follows:

def my_fun(i,k):
#do something
pass

Tn=10
for k in range(Tn+1):
for i in range(0):
my_fun(i,k)


From the above code, we can see that the number of the outer for loop is Tn+1, and the number of the inner for loop is 0, so the number of execution of the function my_fun(i,k) is Tn+1, and the time complexity is O(Tn+1). In terms of time complexity, it is actually a measure defined in an algorithm that varies with the input data size n. Time complexity O(Tn+1) indicates that the relative execution time growth curve is proportional to a constant Tn+1 as the input data size n changes.

dingashuai 注册会员
2023-02-25 12:13

function my_fun(I, k) in the program execution times is $\ frac {n(n - 1)} {2}$, time complexity is $O(n ^ 2)$.

First, the outer loop variable k is traversed in the interval [1, n], so it is executed n times. The inner loop variable i is traversed in the interval [0, k), so for each k, the inner loop executes k times. However, since the function my_fun(i,k) is called once at i!=k, the my_fun(i,k) function will actually only be executed once if i and k are not equal.

Therefore, for each k, the my_fun(i,k) function is executed k-1 times, that is, the number of k-1s other than k is paired with k. Thus, the total number of times my_fun(i,k) is executed is 1+2+3+... +(n-1), that is, $\frac{n(n-1)}{2}$times. Thus, the program's time complexity is $O(n^2)$.

Publish Time
2023-02-25 12:13
Update Time
2023-02-25 12:13