Вопрос о сложности интервью: Если утверждение и сложность сравнения

Question

Я изучал некоторые вопросы интервью и столкнулся с этой проблемой прямо здесь. Изображение вопроса

Я понял все по большей части, кроме той части, которую я выделил красным. Если каждая строка в массиве была отсортирована. Тогда не должна ли сортировка массива занимать только O (журнал a)? Почему они умножили это на O (s)? Это объясняет, что сравнение строк при сортировке заняло бы O (s), где s - наибольший размер строки Это имеет смысл ... Однако я предположил, что сравнение будет выглядеть примерно так ...

if ( array[x].equals(array[y]) ) {...}

Не, если утверждения принимают сложность O (1)? Так не следует ли это игнорировать? Возможно, я ошибаюсь, но я думаю, что я читал, что выполнение операторов if и любых других вложенных операторов (не Loop) потребовало бы сложности O (1). Пожалуйста, поправьте меня, если я ошибаюсь, и научите меня правильно рассчитывать сложность.

Answer 1

Это сортировка, поэтому сравнение будет 'a'> 'b'. Теперь у вас есть две строки:

'aaaaaaaa'
'aaaaaaab'

Потребовалось бы S шагов, чтобы добраться до самого последнего символа, чтобы определить, какая строка больше. Эта операция выполняется для каждого сравнения строк, поэтому мы умножаем ее на S.