Calculating the computational complexity of convolutional neural networks (CNNs) can be a challenging task, but it is crucial for comparing different network architectures. There are several approaches that can be taken to calculate the complexity of CNNs, each with its own advantages and limitations.

One common approach is to count the number of floating-point operations (FLOPs) required to process a single input image. This approach takes into account the number of operations required for each layer, including convolutions, pooling, normalization, and fully connected layers. The FLOPs can be calculated using the number of parameters in each layer and the size of the input feature maps.

Another approach is to count the total number of parameters in the network. This approach is simpler than counting FLOPs, but it may not accurately reflect the computational demands of the network. For example, a network with many small convolutional filters may have a large number of parameters, but may be more computationally efficient than a network with fewer, larger filters.

When comparing networks with different architectures, it is important to consider the specific task the network is designed for. For example, if two networks have similar accuracy on a given task, but one uses convolutional layers while the other uses a different feature extraction method, it may be more appropriate to compare their computational efficiency rather than their total complexity.

In summary, when calculating the complexity of CNNs, it is important to consider both the number of parameters and the computational demands of each layer, and to take into account the specific task the network is designed for.

Great answer above; another thing to consider is the maximum amount of memory that will be required for running inference of a typical input through your network(s). E.g., you should store all the feature maps at layer #i to pass them to layer #(i+1). But afaik this metric is used quite rarely, and so the FLOPs (or, more generally, MACs - multiply and accumulate) and the number of parameters, as suggested by Natha Mohamed above, are the way to go.

What’s not clear is what the complexity of a neural network is supposed to measure.

Thanks for all answers, but this is not exactly that I'm looking for. I'm not looking for kind of comparison between two CNNs, but to compare CNN with classic neural networking without any convolutional layer. What kind of approach should I follow?