Scala Array [Int]: BigO для макс / мин

Question

для массива Int в scala 2.x, каково выражение BigO для массива [Int] .max? а затем, каково выражение для Array [Int] .indexWhere (_ == max)?

Answer 1

Что касается сложности времени или выражения BigO, они оба являются O (n). Поскольку это массив, необходимо пройти по всему массиву, чтобы найти максимум или определить местоположение заданного числа.

Answer 2

Если это не очень плохо реализовано, любой оператор max будет O(n). Вы должны проверять каждое значение один раз (не менее O(n)), и если вы проверяете любое значение более одного раза, вы делаете это неправильно.