Быстрое преобразование Фурье - это алгоритм вычисления
дискретного преобразования фурье. От интеграллов на картинках оно отличается тем, что там не функция от которой береться интеграл, а массив данных, которые как-то суммируются. Оно называется быстрым, потому что там идет вычисление не в лоб по формуле из википедии, а чуть хитрее, за счет чего оно работает быстрее.
В компьютерах используется дискретное преобразование, потому что ну не могут компьютеры работать с бесконечным неприрывным объектом, коим является функция.
И да, там результат - это массив комплексных чисел, поэтому выходные данные в 2 раза больше входных, которые являются вещественными.