Hỏi về cấu trúc dữ liệu, độ phức tạp của bài tính tổng đường chéo chính của ma trận vuông

yujin2020 · October 16, 2020, 5:59am

https://drive.google.com/file/d/1KRnvoML0mBEU__kw-jcymE42or9CbZkR/view?usp=sharing
Đề là tính tổng đường chéo chính của ma trận vuông NxN. Phần dấu ? không biết mình tính có đúng chưa ý và mình cũng chưa rút gọn lại được.

rogp10 · October 17, 2020, 1:54am

Bạn viết thành tổng sigma trước, rồi đổi biến sẽ ra dạng đó là làm đầy đủ.

Mà thuật toán sai, cái này là tính tổng số trong nửa tam giác trên của ma trận.

yujin2020 · October 16, 2020, 2:43pm

À có thể mình dịch sai. Nguyên mẫu câu t.a của thầy mình là: sum of upper primary diagonal N square matrix. Bạn có thể chỉ giúp mình chỗ sigma đó là như thế nào không?
Cảm ơn bạn!

rogp10 · October 17, 2020, 5:34am

Đầu tiên: Khi chỉ tính thân vòng lặp, tổng số lệnh chạy từ i = 1 đến n là \sum_{i=1}^n f(i).

Theo cách tính trên hình ta có:

\sum_{i=0}^{n-1}\ (n+1 - i + \sum_{j=i}^{n-1} 1) + n + 1

Giờ đặt k = n - i và đổi biến.