如何证明算法的时间复杂度？

Question

我对 数据结构 比较陌生，可以在如何证明算法合理性方面得到一些帮助。我相信下面的算法是 O(n + m) 的时间复杂度，因为您独立地遍历了两个不同的数组。您还可以假设数组总是排序的。

public static void intersectionTwoArrays(int[] a, int[] b){
    
        int i = 0;// Index for array a
        int j = 0;// Index for array b
    
        //
        while(i < a.length && j < b.length){
        
            if(a[i] == b[j]){
                System.out.println(a[i]);
                i++;
                j++;
            }
            
            else if(a[i] < b[j]){
                i++;
            }
        
            else if(a[i] > b[j]){
                j++;
            }
            
        }// end while
    
    }// end Method
    
    public static void main(String[] args){
    
        int[] list1 = {0,1,3,5,6,8,10,11};
        int[] list2 = {0,2,3,4,7,8,11};
        
        intersectionTwoArrays(list1, list2);
        
    }// end main

Answer 1

Yep, the time complexity is O(n + m).

The worst case scenario could be such that a consists of consecutive odd integers and b - of consecutive even integers (positive) as below:

a = 1 3 5 ... 2k+1
b = 2 4 6 ... 2k+2

In this case, both i and j will be incremented up to a.length and b.length. That is exactly a.length + b.length steps or O(n + m), where n = a.length and m = b.length

如何证明算法的时间复杂度？

How to justify the time complexity of an algorithm?

java

algorithm

time-complexity