Как вычислить сложность времени

Question

Моя цель - убедиться, что временная сложность операции цикла for не превышает длину обеих строк. Таким образом, в этом примере O (m-n) не может быть больше O (28), если бы я считал правильным. Я почти уверен, что это точно так же, как длина, но я не очень хорошо знаком с Time Complexity.

Итак, мой вопрос в том, какая временная сложность для циклов for?

Итак, я понял, что временная сложность m * n, которая будет больше длины обеих строк. Я знаю, что он нахмурился, но кто-нибудь может понять, как его уменьшить?

Чтобы быть ясным, программа проверяет строку String, чтобы увидеть, содержит ли она какие-либо символы в наборе строк. Если он соответствует, программа должна печатать индекс первого совпадения, чем выход. Это еще одно заявление, которое я собираюсь добавить позже.

Код:

String str = "ThisIsTesTingComplexity"; 
String set = "t9123"; 

for(int j = 0;j<str.length();j++) 
    for(int i = 0;i<set.length();i++) 
     if(str.charAt(j)==set.charAt(i)) 
      System.out.print(j);    

Answer 1

Здесь вы явно имеющие O(n*m) временную сложность в. Просто подсчитайте количество итераций ваших циклов: для каждой итерации первого цикла второй цикл выполняет m итераций и содержит n итераций первого цикла. CQFD.